<!DOCTYPE html><html lang="zh-CN" data-theme="light"><head><meta charset="UTF-8"><meta http-equiv="X-UA-Compatible" content="IE=edge"><meta name="viewport" content="width=device-width, initial-scale=1.0,viewport-fit=cover"><title>数据结构与算法(C/C++实现) | 啊粥啊周舟の部落阁</title><meta name="author" content="Zhouwy"><meta name="copyright" content="Zhouwy"><meta name="format-detection" content="telephone=no"><meta name="theme-color" content="#ffffff"><meta name="description" content="数据结构与算法(C&#x2F;C++实现)​                                                                                                                                参考书籍：《数据结构、算法与应用 C++ 语言描述》 [美]Sartaj Sahni著；C语言中文网 第一章">
<meta property="og:type" content="article">
<meta property="og:title" content="数据结构与算法(C&#x2F;C++实现)">
<meta property="og:url" content="https://gitee.com/zwyywz/zwyywz.git/2021/03/26/DataStructAndAlgorithms/index.html">
<meta property="og:site_name" content="啊粥啊周舟の部落阁">
<meta property="og:description" content="数据结构与算法(C&#x2F;C++实现)​                                                                                                                                参考书籍：《数据结构、算法与应用 C++ 语言描述》 [美]Sartaj Sahni著；C语言中文网 第一章">
<meta property="og:locale" content="zh_CN">
<meta property="og:image" content="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95.jpg">
<meta property="article:published_time" content="2021-03-26T03:20:00.000Z">
<meta property="article:modified_time" content="2023-04-16T13:03:47.067Z">
<meta property="article:author" content="Zhouwy">
<meta property="article:tag" content="算法">
<meta property="article:tag" content="数据结构">
<meta property="article:tag" content="C++">
<meta name="twitter:card" content="summary">
<meta name="twitter:image" content="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95.jpg"><link rel="shortcut icon" href="/zwyywz/img/favicon.png"><link rel="canonical" href="https://gitee.com/zwyywz/zwyywz.git/2021/03/26/DataStructAndAlgorithms/index.html"><link rel="preconnect" href="//cdn.jsdelivr.net"/><link rel="preconnect" href="//busuanzi.ibruce.info"/><link rel="stylesheet" href="/zwyywz/css/index.css"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fortawesome/fontawesome-free/css/all.min.css" media="print" onload="this.media='all'"><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox/fancybox.min.css" media="print" onload="this.media='all'"><script>const GLOBAL_CONFIG = { 
  root: '/zwyywz/',
  algolia: undefined,
  localSearch: undefined,
  translate: {"defaultEncoding":2,"translateDelay":0,"msgToTraditionalChinese":"繁","msgToSimplifiedChinese":"簡"},
  noticeOutdate: undefined,
  highlight: {"plugin":"highlighjs","highlightCopy":true,"highlightLang":true,"highlightHeightLimit":300},
  copy: {
    success: '复制成功',
    error: '复制错误',
    noSupport: '浏览器不支持'
  },
  relativeDate: {
    homepage: true,
    post: true
  },
  runtime: '',
  dateSuffix: {
    just: '刚刚',
    min: '分钟前',
    hour: '小时前',
    day: '天前',
    month: '个月前'
  },
  copyright: {"limitCount":50,"languages":{"author":"作者: Zhouwy","link":"链接: ","source":"来源: 啊粥啊周舟の部落阁","info":"著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"}},
  lightbox: 'fancybox',
  Snackbar: undefined,
  source: {
    justifiedGallery: {
      js: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.js',
      css: 'https://cdn.jsdelivr.net/npm/flickr-justified-gallery/dist/fjGallery.min.css'
    }
  },
  isPhotoFigcaption: false,
  islazyload: false,
  isAnchor: false,
  percent: {
    toc: true,
    rightside: true,
  }
}</script><script id="config-diff">var GLOBAL_CONFIG_SITE = {
  title: '数据结构与算法(C/C++实现)',
  isPost: true,
  isHome: false,
  isHighlightShrink: false,
  isToc: true,
  postUpdate: '2023-04-16 21:03:47'
}</script><noscript><style type="text/css">
  #nav {
    opacity: 1
  }
  .justified-gallery img {
    opacity: 1
  }

  #recent-posts time,
  #post-meta time {
    display: inline !important
  }
</style></noscript><script>(win=>{
    win.saveToLocal = {
      set: function setWithExpiry(key, value, ttl) {
        if (ttl === 0) return
        const now = new Date()
        const expiryDay = ttl * 86400000
        const item = {
          value: value,
          expiry: now.getTime() + expiryDay,
        }
        localStorage.setItem(key, JSON.stringify(item))
      },

      get: function getWithExpiry(key) {
        const itemStr = localStorage.getItem(key)

        if (!itemStr) {
          return undefined
        }
        const item = JSON.parse(itemStr)
        const now = new Date()

        if (now.getTime() > item.expiry) {
          localStorage.removeItem(key)
          return undefined
        }
        return item.value
      }
    }
  
    win.getScript = url => new Promise((resolve, reject) => {
      const script = document.createElement('script')
      script.src = url
      script.async = true
      script.onerror = reject
      script.onload = script.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        script.onload = script.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(script)
    })
  
    win.getCSS = (url,id = false) => new Promise((resolve, reject) => {
      const link = document.createElement('link')
      link.rel = 'stylesheet'
      link.href = url
      if (id) link.id = id
      link.onerror = reject
      link.onload = link.onreadystatechange = function() {
        const loadState = this.readyState
        if (loadState && loadState !== 'loaded' && loadState !== 'complete') return
        link.onload = link.onreadystatechange = null
        resolve()
      }
      document.head.appendChild(link)
    })
  
      win.activateDarkMode = function () {
        document.documentElement.setAttribute('data-theme', 'dark')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#0d0d0d')
        }
      }
      win.activateLightMode = function () {
        document.documentElement.setAttribute('data-theme', 'light')
        if (document.querySelector('meta[name="theme-color"]') !== null) {
          document.querySelector('meta[name="theme-color"]').setAttribute('content', '#ffffff')
        }
      }
      const t = saveToLocal.get('theme')
    
          if (t === 'dark') activateDarkMode()
          else if (t === 'light') activateLightMode()
        
      const asideStatus = saveToLocal.get('aside-status')
      if (asideStatus !== undefined) {
        if (asideStatus === 'hide') {
          document.documentElement.classList.add('hide-aside')
        } else {
          document.documentElement.classList.remove('hide-aside')
        }
      }
    
    const detectApple = () => {
      if(/iPad|iPhone|iPod|Macintosh/.test(navigator.userAgent)){
        document.documentElement.classList.add('apple')
      }
    }
    detectApple()
    })(window)</script><link rel="stylesheet" href="///at.alicdn.com/t/c/font_4018630_wl3l75i04vl.css"><meta name="generator" content="Hexo 6.3.0"></head><body><div id="sidebar"><div id="menu-mask"></div><div id="sidebar-menus"><div class="avatar-img is-center"><img src="/zwyywz/img/avatar.png" onerror="onerror=null;src='/img/friend_404.gif'" alt="avatar"/></div><div class="sidebar-site-data site-data is-center"><a href="/zwyywz/archives/"><div class="headline">文章</div><div class="length-num">17</div></a><a href="/zwyywz/tags/"><div class="headline">标签</div><div class="length-num">29</div></a><a href="/zwyywz/categories/"><div class="headline">分类</div><div class="length-num">5</div></a></div><hr/><div class="menus_items"><div class="menus_item"><a class="site-page" href="/zwyywz/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/zwyywz/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/zwyywz/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 分类</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/zwyywz/note/"><i class="fa-fw iconfont icon-xuexibiji"></i><span> 学习笔记</span></a></li><li><a class="site-page child" href="/zwyywz/opensource/"><i class="fa-fw iconfont icon-xiangmu"></i><span> 开源项目</span></a></li><li><a class="site-page child" href="/zwyywz/development/"><i class="fa-fw iconfont icon-peizhi-xitongpeizhi"></i><span> 环境配置</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 清单</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/zwyywz/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/zwyywz/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/zwyywz/link/"><i class="fa-fw fas fa-link"></i><span> 链接</span></a></div><div class="menus_item"><a class="site-page" href="/zwyywz/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div></div></div><div class="post" id="body-wrap"><header class="post-bg" id="page-header" style="background-image: url('https://blog-1300216920.cos.ap-nanjing.myqcloud.com/数据结构与算法.jpg')"><nav id="nav"><span id="blog-info"><a href="/zwyywz/" title="啊粥啊周舟の部落阁"><span class="site-name">啊粥啊周舟の部落阁</span></a></span><div id="menus"><div class="menus_items"><div class="menus_item"><a class="site-page" href="/zwyywz/"><i class="fa-fw fas fa-home"></i><span> 首页</span></a></div><div class="menus_item"><a class="site-page" href="/zwyywz/archives/"><i class="fa-fw fas fa-archive"></i><span> 时间轴</span></a></div><div class="menus_item"><a class="site-page" href="/zwyywz/tags/"><i class="fa-fw fas fa-tags"></i><span> 标签</span></a></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 分类</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/zwyywz/note/"><i class="fa-fw iconfont icon-xuexibiji"></i><span> 学习笔记</span></a></li><li><a class="site-page child" href="/zwyywz/opensource/"><i class="fa-fw iconfont icon-xiangmu"></i><span> 开源项目</span></a></li><li><a class="site-page child" href="/zwyywz/development/"><i class="fa-fw iconfont icon-peizhi-xitongpeizhi"></i><span> 环境配置</span></a></li></ul></div><div class="menus_item"><a class="site-page group" href="javascript:void(0);"><i class="fa-fw fas fa-list"></i><span> 清单</span><i class="fas fa-chevron-down"></i></a><ul class="menus_item_child"><li><a class="site-page child" href="/zwyywz/music/"><i class="fa-fw fas fa-music"></i><span> 音乐</span></a></li><li><a class="site-page child" href="/zwyywz/movies/"><i class="fa-fw fas fa-video"></i><span> 电影</span></a></li></ul></div><div class="menus_item"><a class="site-page" href="/zwyywz/link/"><i class="fa-fw fas fa-link"></i><span> 链接</span></a></div><div class="menus_item"><a class="site-page" href="/zwyywz/about/"><i class="fa-fw fas fa-heart"></i><span> 关于</span></a></div></div><div id="toggle-menu"><a class="site-page" href="javascript:void(0);"><i class="fas fa-bars fa-fw"></i></a></div></div></nav><div id="post-info"><h1 class="post-title">数据结构与算法(C/C++实现)</h1><div id="post-meta"><div class="meta-firstline"><span class="post-meta-date"><i class="far fa-calendar-alt fa-fw post-meta-icon"></i><span class="post-meta-label">发表于</span><time class="post-meta-date-created" datetime="2021-03-26T03:20:00.000Z" title="发表于 2021-03-26 11:20:00">2021-03-26</time><span class="post-meta-separator">|</span><i class="fas fa-history fa-fw post-meta-icon"></i><span class="post-meta-label">更新于</span><time class="post-meta-date-updated" datetime="2023-04-16T13:03:47.067Z" title="更新于 2023-04-16 21:03:47">2023-04-16</time></span></div><div class="meta-secondline"><span class="post-meta-separator">|</span><span class="post-meta-pv-cv" id="" data-flag-title="数据结构与算法(C/C++实现)"><i class="far fa-eye fa-fw post-meta-icon"></i><span class="post-meta-label">阅读量:</span><span id="busuanzi_value_page_pv"><i class="fa-solid fa-spinner fa-spin"></i></span></span></div></div></div></header><main class="layout" id="content-inner"><div id="post"><article class="post-content" id="article-container"><h1 id="数据结构与算法-C-C-实现"><a href="#数据结构与算法-C-C-实现" class="headerlink" title="数据结构与算法(C/C++实现)"></a>数据结构与算法(C/C++实现)</h1><p>​                                                                                                                                参考书籍：《数据结构、算法与应用 C++ 语言描述》 [美]Sartaj Sahni著；<a target="_blank" rel="noopener" href="http://c.biancheng.net/cpp/biancheng/view/2971.html">C语言中文网</a></p>
<h2 id="第一章-C-回顾"><a href="#第一章-C-回顾" class="headerlink" title="第一章 C++回顾"></a>第一章 C++回顾</h2><h3 id="1-1-C-初步"><a href="#1-1-C-初步" class="headerlink" title="1.1 C++初步"></a>1.1 C++初步</h3><h4 id="1、C-命名空间"><a href="#1、C-命名空间" class="headerlink" title="1、C++命名空间"></a>1、C++命名空间</h4><p>例如小李和小韩都参与了一个文件管理系统的开发，它们都定义了一个全局变量 fp，用来指明前打开的文件，将他们的代码整合在一起编译时，很明显编译器会提示 fp 重复定义（Redefinition）错误。</p>
<p>为了解决合作开发时的命名冲突问题，C++ 引入了<code>命名空间（Namespace）</code>的概念。请看下面的例子：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">namespace</span> Li&#123;  <span class="comment">//小李的变量定义</span></span><br><span class="line">    FILE fp = <span class="literal">NULL</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">namespace</span> Han&#123;  <span class="comment">//小韩的变量定义</span></span><br><span class="line">    FILE fp = <span class="literal">NULL</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>小李与小韩各自定义了以自己姓氏为名的命名空间，此时再将他们的 fp 变量放在一起编译就不会有任何问题。</p>
<blockquote>
<p>命名空间有时也被称为名字空间、名称空间。namespace 是C++中的关键字，用来定义一个命名空间，语法格式为：</p>
</blockquote>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">namespace</span> name&#123;</span><br><span class="line">    <span class="comment">//variables, functions, classes</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><code>name</code>是命名空间的名字，它里面可以包含变量、函数、类、typedef、#define 等，最后由<code>&#123; &#125;</code>包围。</p>
<p>使用变量、函数时要指明它们所在的命名空间。以上面的 fp 变量为例，可以这样来使用：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line">Li :: fp = <span class="built_in">fopen</span>(<span class="string">&quot;one.txt&quot;</span>, <span class="string">&quot;r&quot;</span>);  <span class="comment">//使用小李定义的变量 fp</span></span><br><span class="line">Han :: fp = <span class="built_in">fopen</span>(<span class="string">&quot;two.txt&quot;</span>, <span class="string">&quot;rb+&quot;</span>);  <span class="comment">//使用小韩定义的变量 fp</span></span><br></pre></td></tr></table></figure>
<p><code>::</code>是一个新符号，称为域解析操作符，在C++中用来指明要使用的命名空间。</p>
<p>除了直接使用域解析操作符，还可以采用 using 声明，例如：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">using</span> Li :: fp;</span><br><span class="line">fp = <span class="built_in">fopen</span>(<span class="string">&quot;one.txt&quot;</span>, <span class="string">&quot;r&quot;</span>);  <span class="comment">//使用小李定义的变量 fp</span></span><br><span class="line">Han :: fp = <span class="built_in">fopen</span>(<span class="string">&quot;two.txt&quot;</span>, <span class="string">&quot;rb+&quot;</span>);  <span class="comment">//使用小韩定义的变量 fp</span></span><br></pre></td></tr></table></figure>
<p>在代码的开头用<code>using</code>声明了<code>Li::fp</code>，它的意思是，<code>`using</code>声明以后的程序中如果出现了未指明命名空间的 <code>fp</code>，就使用 <code>Li::fp</code>；但是若要使用小韩定义的<code>fp</code>，仍然需要 <code>Han::fp</code>。</p>
<p>using 声明不仅可以针对命名空间中的一个变量，也可以用于声明整个命名空间，例如：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">using</span> <span class="keyword">namespace</span> Li;</span><br><span class="line">fp = <span class="built_in">fopen</span>(<span class="string">&quot;one.txt&quot;</span>, <span class="string">&quot;r&quot;</span>);  <span class="comment">//使用小李定义的变量 fp</span></span><br><span class="line">Han :: fp = <span class="built_in">fopen</span>(<span class="string">&quot;two.txt&quot;</span>, <span class="string">&quot;rb+&quot;</span>);  <span class="comment">//使用小韩定义的变量 fp</span></span><br></pre></td></tr></table></figure>
<p>如果命名空间 Li 中还定义了其他的变量，那么同样具有 fp 变量的效果。在 using 声明后，如果有未具体指定命名空间的变量产生了命名冲突，那么默认采用命名空间 Li 中的变量。</p>
<p>命名空间内部不仅可以声明或定义变量，对于其它能在命名空间以外声明或定义的名称，同样也都能在命名空间内部进行声明或定义，例如类、函数、typedef、#define 等都可以出现在命名空间中。</p>
<h4 id="2、C-标准库和std命名空间"><a href="#2、C-标准库和std命名空间" class="headerlink" title="2、C++标准库和std命名空间"></a>2、C++标准库和std命名空间</h4><p>为了避免头文件重名，新版 C++ 库也对头文件的命名做了调整，去掉了后缀<code>.h</code>，所以老式 C++ 的<code>iostream.h</code>变成了<code>iostream</code>，<code>fstream.h</code>变成了<code>fstream</code>。而对于原来C语言的头文件，也采用同样的方法，但在每个名字前还要添加一个<code>c</code>字母，所以C语言的<code>stdio.h</code>变成了<code>cstdio</code>，<code>stdlib.h</code>变成了<code>cstdlib</code></p>
<blockquote>
<p>可以发现，对于不带<code>.h</code>的头文件，所有的符号都位于命名空间 std 中，使用时需要声明命名空间 std；对于带<code>.h</code>的头文件，没有使用任何命名空间，所有符号都位于全局作用域。这也是 C++ 标准所规定的</p>
</blockquote>
<p>在C语言中，我们通常会使用 scanf 和 printf 来对数据进行输入输出操作。在C++语言中，C语言的这一套输入输出库我们仍然能使用，但是 C++ 又增加了一套新的、更容易使用的输入输出库。</p>
<p>在C++ 中的输入与输出可以看做是一连串的数据流，输入即可视为从文件或键盘中输入程序中的一串数据流，而输出则可以视为从程序中输出一连串的数据流到显示屏或文件中。在编写 C++ 程序时，如果需要使用输入输出时，则需要包含头文件iostream<code>，包含了用于输入输出的对象，例如常见的</code>cin<code>表示标准输入、</code>cout<code>表示标准输出、</code>cerr`表示标准错误。iostream 是 Input Output Stream 的缩写，意思是“输入输出流”。cout 和 cin 都是 C++ 的内置对象，而不是关键字。</p>
<h4 id="3、new和delete操作符"><a href="#3、new和delete操作符" class="headerlink" title="3、new和delete操作符"></a>3、new和delete操作符</h4><p>在C语言中，动态分配内存用 malloc() 函数，释放内存用 free() 函数。如下所示：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> *p = (<span class="type">int</span>*) <span class="built_in">malloc</span>( <span class="built_in">sizeof</span>(<span class="type">int</span>) * <span class="number">10</span> );  <span class="comment">//分配10个int型的内存空间</span></span><br><span class="line"><span class="built_in">free</span>(p);  <span class="comment">//释放内存</span></span><br></pre></td></tr></table></figure>
<p>在C++中，这两个函数仍然可以使用，但是C++又新增了两个关键字，new 和 delete：new 用来动态分配内存，delete 用来释放内存。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> *p = <span class="keyword">new</span> <span class="type">int</span>;  <span class="comment">//分配1个int型的内存空间</span></span><br><span class="line"><span class="keyword">delete</span> p;  <span class="comment">//释放内存</span></span><br><span class="line"><span class="comment">//new 操作符会根据后面的数据类型来推断所需空间的大小。</span></span><br><span class="line"></span><br><span class="line"><span class="comment">//如果希望分配一组连续的数据，可以使用 new[]：</span></span><br><span class="line"><span class="type">int</span> *p = <span class="keyword">new</span> <span class="type">int</span>[<span class="number">10</span>];  <span class="comment">//分配10个int型的内存空间</span></span><br><span class="line"><span class="keyword">delete</span>[] p;</span><br></pre></td></tr></table></figure>
<p>用 new[] 分配的内存需要用 delete[] 释放，它们是一一对应的。</p>
<p>和 malloc() 一样，new 也是在堆区分配内存，必须手动释放，否则只能等到程序运行结束由操作系统回收。为了避免内存泄露，通常 new 和 delete、new[] 和 delete[] 操作符应该成对出现，并且不要和C语言中 malloc()、free() 一起混用。</p>
<h4 id="4、inline-内联函数"><a href="#4、inline-内联函数" class="headerlink" title="4、inline 内联函数"></a>4、inline 内联函数</h4><blockquote>
<p>一个 C/C++ 程序的执行过程可以认为是多个函数之间的相互调用过程，它们形成了一个或简单或复杂的调用链条，这个链条的起点是 main()，终点也是 main()。当 main() 调用完了所有的函数，它会返回一个值（例如<code>return 0;</code>）来结束自己的生命，从而结束整个程序。</p>
<p>函数调用是有时间和空间开销的。程序在执行一个函数之前需要做一些准备工作，要将实参、局部变量、返回地址以及若干寄存器都压入栈中，然后才能执行函数体中的代码；函数体中的代码执行完毕后还要清理现场，将之前压入栈中的数据都出栈，才能接着执行函数调用位置以后的代码。</p>
<p>如果函数体代码比较多，需要较长的执行时间，那么函数调用机制占用的时间可以忽略；如果函数只有一两条语句，那么大部分的时间都会花费在函数调用机制上，这种时间开销就就不容忽视。</p>
<p>为了消除函数调用的时空开销，C++ 提供一种提高效率的方法，即在编译时将函数调用处用函数体替换，类似于C语言中的宏展开。这种在函数调用处直接嵌入函数体的函数称为<code>`内联函数（Inline Function）</code>，又称内嵌函数或者内置函数。</p>
</blockquote>
<p>注意，要在函数定义处添加 inline 关键字，在函数声明处添加 inline 关键字虽然没有错，但这种做法是无效的，编译器会忽略函数声明处的 inline 关键字。</p>
<p><strong>使用内联函数的缺点也是非常明显的，编译后的程序会存在多份相同的函数拷贝，如果被声明为内联函数的函数体非常大，那么编译后的程序体积也将会变得很大，所以再次强调，一般只将那些短小的、频繁调用的函数声明为内联函数。</strong></p>
<h3 id="1-2-C-函数提高"><a href="#1-2-C-函数提高" class="headerlink" title="1.2 C++ 函数提高"></a>1.2 C++ 函数提高</h3><h4 id="1、函数参数"><a href="#1、函数参数" class="headerlink" title="1、函数参数"></a>1、函数参数</h4><p><strong>1、传值参数</strong></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">abc</span><span class="params">(<span class="type">int</span> a ,<span class="type">int</span> b,<span class="type">int</span>)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">	<span class="keyword">return</span> a+b+c;	</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>a,b,c是<code>形参</code>，每一个形参都是整形；可以使z=abc(2,x,y)调用求和函数。那么2,x,y分别对应a,b,c的实参。形参a,b,c实际上是<code>传值参数</code>，在运行时，函数a,b,c执行前，把实参复制给形参。复制过程是由形参类型的<code>复制构造函数</code></p>
<p><strong>2、默认参数</strong></p>
<p>在C++中，函数的形参列表中的形参是可以有默认值的</p>
<p>语法：<code>返回值类型 函数名(参数A=默认值1，参数B=默认值2)</code></p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">add</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b = <span class="number">10</span>, <span class="type">int</span> c = <span class="number">20</span>)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> a + b + c;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//如果某个位置有默认参数，那么从这个位置往后，都必须有默认值</span></span><br><span class="line"><span class="comment">//声明和实现只能一个有默认参数</span></span><br><span class="line"></span><br><span class="line"><span class="comment">/*错误示例</span></span><br><span class="line"><span class="comment">int add(int a, int b = 10, int c)</span></span><br><span class="line"><span class="comment">&#123;</span></span><br><span class="line"><span class="comment">    return a + b + c;</span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"><span class="comment">*/</span></span><br></pre></td></tr></table></figure>
<h4 id="2、函数重载"><a href="#2、函数重载" class="headerlink" title="2、函数重载"></a>2、函数重载</h4><p><strong>作用：</strong>函数名相同，提高复用性</p>
<p>函数重载满足的条件：</p>
<ul>
<li>同一个作用域下</li>
<li>函数名称相同</li>
<li>函数参数类型不同，或者个数不同，或者顺序不同</li>
</ul>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">int</span> <span class="title">add</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> a + b;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">add</span><span class="params">(<span class="type">int</span> a, <span class="type">int</span> b, <span class="type">int</span> c)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> a + b + c;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">double</span> <span class="title">add</span><span class="params">(<span class="type">double</span> a, <span class="type">double</span> b, <span class="type">double</span> c)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> a + b + c;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="function"><span class="type">int</span> <span class="title">main</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="type">int</span> m, n;</span><br><span class="line">    cout &lt;&lt; <span class="string">&quot; 1 : &quot;</span> &lt;&lt; <span class="built_in">add</span>(<span class="number">1</span>, <span class="number">2</span>) &lt;&lt; endl;</span><br><span class="line">    cout &lt;&lt; <span class="string">&quot; 2 : &quot;</span> &lt;&lt; <span class="built_in">add</span>(<span class="number">1</span>, <span class="number">2</span>, <span class="number">3</span>) &lt;&lt; endl;</span><br><span class="line">    cout &lt;&lt; <span class="string">&quot; 3 : &quot;</span> &lt;&lt; <span class="built_in">add</span>(<span class="number">1.1</span>, <span class="number">2.2</span>, <span class="number">3.3</span>) &lt;&lt; endl;</span><br><span class="line">    <span class="built_in">system</span>(<span class="string">&quot;pause&quot;</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>函数重载的注意事项：</p>
<ul>
<li>引用作为函数重载的条件</li>
<li>函数重载碰到默认参数</li>
</ul>
<p>==注意：编译器的二义性==</p>
<h4 id="3、模板函数"><a href="#3、模板函数" class="headerlink" title="3、模板函数"></a>3、模板函数</h4><p>假定我们希望编写另外一个函数来计算相同的表达式，不过这次a、b和c是float类型，结果也是float类型。程序1-2中给出了具体的代码。区别仅在于形参以及函数返回值的类型不同。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br></pre></td><td class="code"><pre><span class="line"><span class="function"><span class="type">float</span> <span class="title">abc</span><span class="params">(<span class="type">float</span> a, <span class="type">float</span> b, <span class="type">float</span> c)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> a+b+c;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>与其对每一种可能的形参类型都编写一个相应函数的新版本，不如编写一段通用代码,它的参数类型是一个变量，它的值由编译器来确定。这种通用代码使用的是模板语句。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">class</span> <span class="title class_">T</span>&gt;</span><br><span class="line"><span class="function">T <span class="title">abc</span><span class="params">(T a, T b, T c)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">return</span> a+b+c;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>从这段通用代码，编译器通过既可T替换为int,也可把T替换为float 。事实上，通过把T替换为double或long,编译器还可以构造出函数abc的双精度型版本和长整型版本。把函数abc编写成模板函数,我们就不必了解形参的类型了。</p>
<h3 id="1-3-C-类和对象"><a href="#1-3-C-类和对象" class="headerlink" title="1.3 C++类和对象"></a>1.3 C++类和对象</h3><p>C++面向对象的三大特性：==封装、继承、多态==，C++任务万事万物皆为对象，对象有其属性和行为。</p>
<p>类是创建对象的模板，一个类可以创建多个对象，每个对象都是类类型的一个变量；创建对象的过程也叫类的实例化。每个对象都是类的一个具体实例，拥有类的成员变量和成员函数。</p>
<blockquote>
<p>有些教程将类的成员变量称为类的属性（Property），将类的成员函数称为类的方法（Method）。在面向对象的编程语言中，经常把函数（Function）称为方法（Method）。</p>
</blockquote>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Student</span></span><br><span class="line">&#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="comment">//属性（Property）</span></span><br><span class="line">    string name;</span><br><span class="line">    <span class="type">int</span> old;</span><br><span class="line">    <span class="type">float</span> score;</span><br><span class="line">	<span class="comment">//方法（Method）</span></span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">StudentInformation</span><span class="params">()</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        cout &lt;&lt; <span class="string">&quot;the old of &quot;</span> &lt;&lt; name &lt;&lt; <span class="string">&quot;is &quot;</span> &lt;&lt; old &lt;&lt; <span class="string">&quot;,&quot;</span></span><br><span class="line">             &lt;&lt; <span class="string">&quot;and his(her) score is &quot;</span> &lt;&lt; score &lt;&lt; endl;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h4 id="1、封装的意义"><a href="#1、封装的意义" class="headerlink" title="1、封装的意义"></a>1、封装的意义</h4><p><strong>访问的三种权限：</strong></p>
<p><code>公共权限（public）</code>：成员 类内可以访问 类外可以访问</p>
<p><code>保护权限（protected）</code>：成员  类内可以访问  类外不可以访问  子类可以访问父类</p>
<p><code>私有权限（private）</code>：成员  类内可以访问  类外不可以访问 子类不可以访问父类</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Person</span></span><br><span class="line">&#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    string m_name;</span><br><span class="line"><span class="keyword">protected</span>:</span><br><span class="line">    <span class="type">int</span> m_car;</span><br><span class="line"><span class="keyword">private</span>:</span><br><span class="line">    <span class="type">int</span> m_card_ID;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="function"><span class="type">void</span> <span class="title">func</span><span class="params">()</span></span></span><br><span class="line"><span class="function">    </span>&#123;</span><br><span class="line">        m_name = <span class="string">&quot;zwy&quot;</span>;</span><br><span class="line">        m_car = <span class="number">123</span>;</span><br><span class="line">        m_card_ID = <span class="number">123456</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<p><strong>成员属性设置为私有</strong></p>
<p>1、可以自己控制读写属性</p>
<p>2、对于写可以检测数据有效性</p>
<h4 id="2、对象的初始化和清理"><a href="#2、对象的初始化和清理" class="headerlink" title="2、对象的初始化和清理"></a>2、对象的初始化和清理</h4><p><strong>1、构造函数和析构函数</strong></p>
<p> <strong>构造函数语法</strong>：<code>类名（）&#123;&#125;</code></p>
<ul>
<li>构造函数没有返回值，也不写void</li>
<li>函数名与类名相同</li>
<li>构造函数也可以有参数，因此也可以发生重载</li>
<li>程序在调用对象的时候自动调用构造，无需手动调用，而且只会调用一次</li>
</ul>
<p>析构函数语法：<code>~类名（）&#123;&#125;</code></p>
<ul>
<li>析构函数没有返回值，也不写void</li>
<li>函数名与类名相同，在名称前加上符号 ~</li>
<li>析构函数不可以有参数，因此不可以发生重载</li>
<li>程序在对象销毁的时候自动调用析构，无需手动调用，而且只会调用一次</li>
</ul>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Person</span></span><br><span class="line">&#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    <span class="built_in">Person</span>()</span><br><span class="line">    &#123;</span><br><span class="line">        cout &lt;&lt; <span class="string">&quot;1&quot;</span> &lt;&lt; endl;</span><br><span class="line">    &#125;</span><br><span class="line"></span><br><span class="line">    ~<span class="built_in">Person</span>()</span><br><span class="line">    &#123;</span><br><span class="line">         cout &lt;&lt; <span class="string">&quot;2&quot;</span> &lt;&lt; endl;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<p><strong>2、构造函数的分类</strong></p>
<ul>
<li><p>按照参数分类：无参构造（默认构造）和有参构造</p>
</li>
<li><p>按照类型分类：拷贝构造 和 普通构造（默认构造）</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//有参构造  </span></span><br><span class="line"><span class="built_in">Person</span>(<span class="type">int</span> a)</span><br><span class="line">&#123;</span><br><span class="line">    cout &lt;&lt; <span class="string">&quot;1&quot;</span> &lt;&lt; endl;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//拷贝构造</span></span><br><span class="line"><span class="built_in">Person</span>(<span class="type">const</span> Person &amp;p)</span><br><span class="line">&#123;</span><br><span class="line">    <span class="comment">//将传入类的所有属性拷贝到本个上</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
</li>
</ul>
<h4 id="3、函数模板"><a href="#3、函数模板" class="headerlink" title="3、函数模板"></a>3、函数模板</h4><ul>
<li><p>C++另一种编程思想称为泛型编程。主要利用的技术就是模板</p>
</li>
<li><p>C++提供两种模板机制:函数模板和类模板</p>
</li>
</ul>
<p>  <strong>函数模板语法：</strong></p>
  <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//定义</span></span><br><span class="line"><span class="function"><span class="keyword">template</span>&lt;<span class="keyword">typename</span> T&gt;</span></span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">func</span><span class="params">(T &amp;a,T &amp;b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    </span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//使用</span></span><br><span class="line"><span class="built_in">func</span>&lt;datatype&gt;(a,b) ;</span><br></pre></td></tr></table></figure>
<p>  <strong>解释：</strong></p>
<p>  ​    template ———声明模板</p>
<p>  ​    typename ——— 表明其后面的是一种数据类型，可用class替换</p>
<p>  ​    T ——— 通用数据类型，名称可替换，通常为大写字母</p>
<p>  <strong>函数模板作用:</strong>  建立-一个通用函数，其函数返回值类型和形参类型可以不具体制定,用-个虚拟的类型来代表。</p>
<p>  <strong>函数模板的局限性</strong>：假设有个类—人，它有两个属性—名字和年龄。能否通过函数模板直接判断是否是同一个人？</p>
  <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">class</span> <span class="title class_">Person</span>&#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    string _name;</span><br><span class="line">    <span class="type">int</span> _age;</span><br><span class="line">    <span class="built_in">Person</span>(string name, <span class="type">int</span> age) : _name(name), _age(age)&#123;&#125;;</span><br><span class="line">    ~<span class="built_in">Person</span>()&#123;&#125;;</span><br><span class="line">&#125;;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p>以下为错误示例:</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">/*</span></span><br><span class="line"><span class="comment">template &lt;typename T&gt;</span></span><br><span class="line"><span class="comment">bool func(T &amp;a, T &amp;b)</span></span><br><span class="line"><span class="comment">&#123;</span></span><br><span class="line"><span class="comment">    if (a == b)</span></span><br><span class="line"><span class="comment">        return true;</span></span><br><span class="line"><span class="comment">    else</span></span><br><span class="line"><span class="comment">        return false;</span></span><br><span class="line"><span class="comment">&#125;</span></span><br><span class="line"><span class="comment">void test_1()</span></span><br><span class="line"><span class="comment">&#123;</span></span><br><span class="line"><span class="comment">    Person P1(&quot;Tom&quot;, 10);</span></span><br><span class="line"><span class="comment">    Person P2(&quot;Tom&quot;, 10);</span></span><br><span class="line"><span class="comment">    bool re = func(P1, P2);</span></span><br><span class="line"><span class="comment">&#125;*/</span></span><br></pre></td></tr></table></figure>
<p><strong>解决方法</strong>：</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">typename</span> T&gt;</span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">func</span><span class="params">(T &amp;a, T &amp;b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (a == b)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="keyword">template</span> &lt;&gt;</span><br><span class="line"><span class="function"><span class="type">bool</span> <span class="title">func</span><span class="params">(Person &amp;a, Person &amp;b)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (a._age == b._age &amp;&amp; a._name == b._name)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">true</span>;</span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">        <span class="keyword">return</span> <span class="literal">false</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">test_2</span><span class="params">()</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="function">Person <span class="title">P1</span><span class="params">(<span class="string">&quot;Tom&quot;</span>, <span class="number">10</span>)</span></span>;</span><br><span class="line">    <span class="function">Person <span class="title">P2</span><span class="params">(<span class="string">&quot;Tom&quot;</span>, <span class="number">10</span>)</span></span>;</span><br><span class="line">    <span class="type">bool</span> re = <span class="built_in">func</span>&lt;Person&gt;(P1, P2);</span><br><span class="line">    cout &lt;&lt; re &lt;&lt; endl;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h4 id="4、类模板"><a href="#4、类模板" class="headerlink" title="4、类模板"></a>4、类模板</h4><p>  <strong>类模板语法：</strong></p>
  <figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">class</span> <span class="title class_">nameType</span>, <span class="keyword">class</span> <span class="title class_">ageType</span> = <span class="type">int</span>&gt;</span><br><span class="line"><span class="keyword">class</span> Person</span><br><span class="line">&#123;</span><br><span class="line"><span class="keyword">public</span>:</span><br><span class="line">    nameType _name;</span><br><span class="line">    ageType _age;</span><br><span class="line">    <span class="built_in">Person</span>(nameType name, ageType age) : _name(name), _age(age)&#123;&#125;;</span><br><span class="line">    ~<span class="built_in">Person</span>()&#123;&#125;;</span><br><span class="line">&#125;;</span><br></pre></td></tr></table></figure>
<p>  <strong>解释：</strong></p>
<p>  ​    template ———声明模板</p>
<p>  ​    typename ——— 表明其后面的是一种数据类型，可用class替换</p>
<p>  ​    T ——— 通用数据类型，名称可替换，通常为大写字母</p>
<h2 id="第二章-程序性能分析"><a href="#第二章-程序性能分析" class="headerlink" title="第二章 程序性能分析"></a>第二章 程序性能分析</h2><h3 id="2-1-空间复杂度"><a href="#2-1-空间复杂度" class="headerlink" title="2.1 空间复杂度"></a>2.1 空间复杂度</h3><p><strong>1 、空间复杂度的组成</strong><br>    程序所需要的空间主要由以下部分构成:<br>        (1)指令空间( instruction space )：指令空间是指编译之后的程序指令所需要的存储空间。</p>
<p>​    指令空间的数量取决于如下因素:<br>​            ●把程序转换成机器代码的编译器。<br>​            ●在编译时的编译器选项。<br>​            ●目标计算机。</p>
<p>(2)数据空间( data space )：数据空间是指所有常量和变量值所需要的存储空间。它由两个部分构成:</p>
<p>​    ●常量和简单变量所需要的存储空间。<br>​            ●动态数组和动态类实例等动态对象所需要的空间。</p>
<div class="table-container">
<table>
<thead>
<tr>
<th style="text-align:center">类型</th>
<th style="text-align:center">空间大小</th>
<th style="text-align:center">范围</th>
</tr>
</thead>
<tbody>
<tr>
<td style="text-align:center">bool</td>
<td style="text-align:center">1</td>
<td style="text-align:center">{true,flase}</td>
</tr>
<tr>
<td style="text-align:center">char</td>
<td style="text-align:center">1</td>
<td style="text-align:center">{-128,127}</td>
</tr>
<tr>
<td style="text-align:center">unsigned char</td>
<td style="text-align:center">1</td>
<td style="text-align:center">{0,255}</td>
</tr>
<tr>
<td style="text-align:center">short</td>
<td style="text-align:center">2</td>
<td style="text-align:center">{-32768,32767}</td>
</tr>
<tr>
<td style="text-align:center">unsigned short</td>
<td style="text-align:center">2</td>
<td style="text-align:center">{0,65535}</td>
</tr>
<tr>
<td style="text-align:center">long</td>
<td style="text-align:center">4</td>
<td style="text-align:center">{-2<sup>31</sup>,-2<sup>31</sup>-1}</td>
</tr>
<tr>
<td style="text-align:center">unsigned long</td>
<td style="text-align:center">4</td>
<td style="text-align:center">{0,2<sup>32</sup>-1}</td>
</tr>
<tr>
<td style="text-align:center">int</td>
<td style="text-align:center">4</td>
<td style="text-align:center">{-2<sup>31</sup>,-2<sup>31</sup>-1}</td>
</tr>
<tr>
<td style="text-align:center">unsigned int</td>
<td style="text-align:center">4</td>
<td style="text-align:center">{0,2<sup>32</sup>-1}</td>
</tr>
<tr>
<td style="text-align:center">float</td>
<td style="text-align:center">4</td>
<td style="text-align:center">+-3.4E+-38 (7位)</td>
</tr>
<tr>
<td style="text-align:center">double</td>
<td style="text-align:center">8</td>
<td style="text-align:center">+-1.7E+-308(15位)</td>
</tr>
<tr>
<td style="text-align:center">long double</td>
<td style="text-align:center">10</td>
<td style="text-align:center">+-1.2E+-4392(19位)</td>
</tr>
</tbody>
</table>
</div>
<p>(3)环境栈空间( environment stack space )：环境栈用来保存暂停的陋数和方法在恢复运行时所需要的信息。例如，如果函数foo调用了丽数goo,那么我们至少要保存在函数goo结束时函数foo继续执行的指令地址。</p>
<p>●返回地址。<br>        ●正在调用的函数的所有局部变量的值以及形式参数的值( 仅对递归函数而言)。</p>
<h3 id="2-2-时间复杂度"><a href="#2-2-时间复杂度" class="headerlink" title="2.2 时间复杂度"></a>2.2 时间复杂度</h3><h3 id="2-3-操作计数"><a href="#2-3-操作计数" class="headerlink" title="2.3 操作计数"></a>2.3 操作计数</h3><h3 id="2-4-步数"><a href="#2-4-步数" class="headerlink" title="2.4 步数"></a>2.4 步数</h3><h2 id="第三章-线性表——数组描述"><a href="#第三章-线性表——数组描述" class="headerlink" title="第三章  线性表——数组描述"></a>第三章  线性表——数组描述</h2><h3 id="3-1-线性表的数据结构"><a href="#3-1-线性表的数据结构" class="headerlink" title="3.1 线性表的数据结构"></a>3.1 线性表的数据结构</h3><p><strong>线性表( linear list)</strong>也称<strong>有序表( ordered list)</strong>, 它的每一个实例都是元素的一一个有序集合。每一个实例的形式为(e<sub>0</sub>,e<sub>1</sub>,e<sub>2</sub>,e<sub>3</sub>…e<sub>n</sub>)其中n是有穷自然数，e<sub>i</sub> 是线性表的元素，i是元素e<sub>i</sub> 的索引，n是线性表的长度或大小。元素可以被看做原子，它们本身的结构与线性表的结构无关。当n=0时，线性表为空;当n&gt;0时，e<sub>0</sub>是线性表的第0个元素或首元素, e<sub>n-1</sub> 是线性表的最后一个元素。可以认为e<sub>0</sub>先于e<sub>1</sub>，e<sub>1</sub>先于e<sub>2</sub>等等。除了这种先后关系之外，线性表不再有其他关系。</p>
<p><strong>对线性表的操作</strong>：</p>
<ul>
<li>创建线性表</li>
</ul>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">ChaLenArray *<span class="title function_">Init_Array</span><span class="params">()</span> <span class="comment">//初始化一个动态数组</span></span><br><span class="line">&#123;</span><br><span class="line">    ChaLenArray *NewArray = (ChaLenArray *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(ChaLenArray));</span><br><span class="line">    NewArray-&gt;size = <span class="number">0</span>;</span><br><span class="line">    NewArray-&gt;cap = <span class="number">20</span>;</span><br><span class="line">    NewArray-&gt;pAddr = (<span class="type">int</span> *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(<span class="type">int</span>) * NewArray-&gt;cap);</span><br><span class="line">    <span class="keyword">return</span> NewArray;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li>撤销一个线性表。</li>
</ul>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">void</span> <span class="title function_">FreeSpace_Array</span><span class="params">(ChaLenArray *arr)</span> <span class="comment">//释放一个动态数组内存空间</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span> (arr-&gt;pAddr != <span class="literal">NULL</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">/* code */</span></span><br><span class="line">        <span class="built_in">free</span>(arr-&gt;pAddr);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">free</span>(arr);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li>确定线性表的长度。</li>
</ul>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">Size_Array</span><span class="params">(ChaLenArray *arr)</span></span><br><span class="line">&#123;</span><br><span class="line"><span class="keyword">if</span> (arr == <span class="literal">NULL</span>)</span><br><span class="line"><span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line"><span class="keyword">return</span> arr-&gt;size;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li>按一个给定的索引查找一个元素。</li>
</ul>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">At_Array</span><span class="params">(ChaLenArray *arr, <span class="type">int</span> pos)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">return</span> arr-&gt;pAddr[pos];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li>按一个给定的元素查找其索引。</li>
</ul>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">Find_Array</span><span class="params">(ChaLenArray *arr, <span class="type">int</span> value)</span> <span class="comment">//找到一个元素</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    <span class="type">int</span> pos = <span class="number">-1</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; arr-&gt;size; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span> (arr-&gt;pAddr[i] == value)</span><br><span class="line">        &#123;</span><br><span class="line">            pos = i;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> pos;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li>按一个给定的索引删除- -个元素。</li>
</ul>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">void</span> <span class="title function_">RemoveByPos_Array</span><span class="params">(ChaLenArray *arr, <span class="type">int</span> pos)</span> <span class="comment">//通过位置删除一个元素</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span> (pos &lt; <span class="number">0</span> || pos &gt;= arr-&gt;size)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = pos; i &lt; arr-&gt;size - <span class="number">1</span>; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        arr-&gt;pAddr[i] = arr-&gt;pAddr[i + <span class="number">1</span>];</span><br><span class="line">    &#125;</span><br><span class="line">    arr-&gt;size--;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li>按一个给定的索引插入-一个元素。</li>
</ul>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">void</span> <span class="title function_">Push_Back_Array</span><span class="params">(ChaLenArray *arr, <span class="type">int</span> value)</span> <span class="comment">//尾部插入一个数据</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span> (arr-&gt;size &gt;= arr-&gt;cap)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="type">int</span> *Newspce = (<span class="type">int</span> *)<span class="built_in">malloc</span>(arr-&gt;cap * <span class="number">2</span> * <span class="keyword">sizeof</span>(<span class="type">int</span>));</span><br><span class="line">        <span class="built_in">memcpy</span>(Newspce, arr-&gt;pAddr, arr-&gt;cap * <span class="keyword">sizeof</span>(<span class="type">int</span>));</span><br><span class="line">        <span class="built_in">free</span>(arr-&gt;pAddr);</span><br><span class="line">        arr-&gt;cap = arr-&gt;cap * <span class="number">2</span>;</span><br><span class="line">        arr-&gt;pAddr = Newspce;</span><br><span class="line">    &#125;</span><br><span class="line">    arr-&gt;pAddr[arr-&gt;size] = value;</span><br><span class="line">    arr-&gt;size++;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<ul>
<li>从左至右顺序输出线性表元素。</li>
</ul>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">void</span> <span class="title function_">Printf_Array</span><span class="params">(ChaLenArray *arr)</span> <span class="comment">//打印</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (arr == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; arr-&gt;size; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">/* code */</span></span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;%d &quot;</span>, arr-&gt;pAddr[i]);</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;\n&quot;</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="3-2-变长一维数组"><a href="#3-2-变长一维数组" class="headerlink" title="3.2 变长一维数组"></a>3.2 变长一维数组</h3><p>一维数组array,线性表元素存在array[0,n-1]中，要增加或减少这个数组长度，首先要创建一个新数组，然后把array复制到这个数组，最后改变数组array的值，是它能够引用新数组。</p>
<figure class="highlight c++"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//c++实现</span></span><br><span class="line"><span class="keyword">template</span> &lt;<span class="keyword">class</span> <span class="title class_">T</span>&gt;</span><br><span class="line"><span class="function"><span class="type">void</span> <span class="title">ChangeLength1D</span><span class="params">(T *a, <span class="type">int</span> OldLength, <span class="type">int</span> NewLength)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="comment">//if (NewLength &lt;= 0)</span></span><br><span class="line">    <span class="comment">//    throw &quot;new length must be &gt;=0&quot;;</span></span><br><span class="line">    T *temp = <span class="keyword">new</span> T[NewLength];</span><br><span class="line">    <span class="type">int</span> number = <span class="built_in">min</span>(OldLength, NewLength);</span><br><span class="line">    <span class="built_in">copy</span>(a, a + number, temp);</span><br><span class="line">    <span class="keyword">delete</span>[] temp;</span><br><span class="line">    a = temp;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//C语言实现</span></span><br><span class="line"><span class="function">ChaLenArray *<span class="title">Expand_Capacity</span><span class="params">(ChaLenArray *old_arr)</span></span></span><br><span class="line"><span class="function"></span>&#123;</span><br><span class="line">    <span class="keyword">if</span> (old_arr == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="literal">NULL</span>;</span><br><span class="line">    ChaLenArray *New_arr;</span><br><span class="line">    New_arr-&gt;cap = (<span class="type">int</span> *)<span class="built_in">malloc</span>(<span class="built_in">sizeof</span>(<span class="type">int</span>) * old_arr-&gt;cap * <span class="number">2</span>);</span><br><span class="line">    <span class="built_in">memcpy</span>(New_arr-&gt;pAddr, old_arr-&gt;pAddr, old_arr-&gt;cap * <span class="built_in">sizeof</span>(<span class="type">int</span>));</span><br><span class="line">    New_arr-&gt;size = old_arr-&gt;size;</span><br><span class="line">    <span class="built_in">free</span>(old_arr-&gt;pAddr);</span><br><span class="line">    <span class="keyword">return</span> New_arr;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="第四章-线性表——-链表"><a href="#第四章-线性表——-链表" class="headerlink" title="第四章 线性表—— 链表"></a>第四章 线性表—— 链表</h2><h3 id="4-1-单向链表"><a href="#4-1-单向链表" class="headerlink" title="4.1 单向链表"></a>4.1 单向链表</h3><p>在链式描述中，数据实例的每一个元素都用一个单元或节点来描述。节点不必是数组成员，因此不是用公式来确定元素的位置。取而代之的是，每一个节点都明确包含另一个相关节点的位置信息，这个信息称为<code>链( link )</code>或<code>指针( pointer )</code>。</p>
<p><img src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/image-20210409083321017.png" alt=""></p>
<p>一般来说，为了找到索引为theIndex的元素，需要从firstNode开始，跟踪theIndex个指针才能找到。一个线 性表的链式的每一个节点只有一个链，这种结构称为<code>单向链表( singly linkedlist)</code>。链表从左到右，每一个节点(最后一个节点除外)都链接着下一个节点，最后一个节点的链域值为NULL。这样的结构也称为<code>链条( chain )</code>。</p>
<p>因此，定义数据类型如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//定义节点</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">LINKNODE</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="type">void</span> *data; <span class="comment">//指向任何数据指针 （数据域）</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">LINKNODE</span> *<span class="title">next</span>;</span><span class="comment">//指向下一个节点 （指针域）</span></span><br><span class="line">&#125; LinkNode;</span><br><span class="line"><span class="comment">//定义链表</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">LINKLIST</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    LinkNode *head;<span class="comment">//定义头结点</span></span><br><span class="line">    <span class="type">int</span> size;<span class="comment">//定义链表长度</span></span><br><span class="line">&#125; LinKList;</span><br></pre></td></tr></table></figure>
<p><code>初始化</code>：首先需要初始化链表，对于一个链表而言，只需初始化头结点的指针域和数据域。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br></pre></td><td class="code"><pre><span class="line">LinKList *<span class="title function_">Init_LinkList</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">    LinKList *<span class="built_in">list</span> = (LinKList *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(LinKList));<span class="comment">//申请内存存放链表</span></span><br><span class="line">    <span class="built_in">list</span>-&gt;size = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">list</span>-&gt;head = (LinkNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(LinkNode));<span class="comment">//申请内存存放头结点</span></span><br><span class="line">    <span class="built_in">list</span>-&gt;head-&gt;data = <span class="literal">NULL</span>;<span class="comment">//头结点的数据域</span></span><br><span class="line">    <span class="built_in">list</span>-&gt;head-&gt;next = <span class="literal">NULL</span>;<span class="comment">//头结点的指针域</span></span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><code>插入元素</code>: 将要插入的元素与表List、位置Pos和数据指针Data一起传入。这个 Insert_LinkList（）函数将一个元索插人到由 Pos所指示的位置之后。它意味着插入操作如何实现并没有完全确定的规则。很有可能将新元素插人到位置Pos处(即在位置P处当时的元索的前面),所以需要知道位置P前面的元素。</p>
<p><img src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/链表插入.png" alt=""></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">void</span> <span class="title function_">Insert_LinkList</span><span class="params">(LinKList *List, <span class="type">int</span> Pos, <span class="type">void</span> *Data)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">list</span> == <span class="literal">NULL</span> || data == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span> (pos &lt; <span class="number">0</span> || pos &gt; <span class="built_in">list</span>-&gt;size)</span><br><span class="line">        pos = <span class="built_in">list</span>-&gt;size;</span><br><span class="line">    <span class="comment">//创建新节点</span></span><br><span class="line">    LinkNode *newNode = (LinkNode*)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(LinkNode));</span><br><span class="line">    newNode-&gt;data = data;</span><br><span class="line">    newNode-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">    <span class="comment">//找节点（即找到Pos-1位置）</span></span><br><span class="line">    LinkNode *pCurrent = <span class="built_in">list</span>-&gt;head; <span class="comment">//辅助指针</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; pos; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        pCurrent = pCurrent-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//新节点入链表</span></span><br><span class="line">    newNode-&gt;next = pCurrent-&gt;next;</span><br><span class="line">    pCurrent-&gt;next = newNode;</span><br><span class="line">    <span class="built_in">list</span>-&gt;size++;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><code>删除元素</code>: 通过位置删除表List中的某个元素X。需要获取元素X的位置，与插入操作相同，也许寻找出前一个元素，并且缓存前一个元素的指针域信息，将指针域信息指向Pos的下一个位置。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">void</span> <span class="title function_">RemoveByBos_linkList</span><span class="params">(LinKList *<span class="built_in">list</span>, <span class="type">int</span> pos)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">list</span> == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="keyword">if</span> (pos &lt; <span class="number">0</span> || pos &gt;= <span class="built_in">list</span>-&gt;size)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    <span class="comment">//查找删除的前一个节点</span></span><br><span class="line">    LinkNode *pCurrent = <span class="built_in">list</span>-&gt;head;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; pos; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        pCurrent = pCurrent-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//缓存待删除的节点</span></span><br><span class="line">    LinkNode *pDel = pCurrent-&gt;next;</span><br><span class="line">    pCurrent-&gt;next = pDel-&gt;next-&gt;next;</span><br><span class="line">    <span class="comment">//释放删除节点的内存</span></span><br><span class="line">    <span class="built_in">free</span>(pDel);</span><br><span class="line">    <span class="built_in">list</span>-&gt;size--;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><code>查找元素</code>: 在链表中查找指定数据元素，最常用的方法是：从表头依次遍历表中节点，用被查找元素与各节点数据域中存储的数据元素进行比对。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">Find_LinkList</span><span class="params">(LinKList *<span class="built_in">list</span>, <span class="type">void</span> *data)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">list</span> == <span class="literal">NULL</span> || data == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    <span class="type">int</span> i;</span><br><span class="line">    LinkNode *pCurrent = <span class="built_in">list</span>-&gt;head-&gt;next;</span><br><span class="line">    <span class="keyword">while</span> (pCurrent != <span class="literal">NULL</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span> (pCurrent-&gt;data == data)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">break</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        i++;</span><br><span class="line">        pCurrent = pCurrent-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> i;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><code>打印输出</code>：遍历链表中的所有元素，直到最后一个元素为<code>NULL</code>,这里为了打印任何类型的数据，使用了函数指针，重定义了Print函数。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">void</span> <span class="title function_">MyPrint</span><span class="params">(<span class="type">void</span> *data)</span></span><br><span class="line">&#123;</span><br><span class="line">    PERSON *p = (PERSON *)data;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;Name:%s Age:%d Score:%d\n&quot;</span>, p-&gt;name, p-&gt;age, p-&gt;score);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">void</span> <span class="title function_">Printf_LinkList</span><span class="params">(LinKList *<span class="built_in">list</span>, PRINTFLINKNODE print)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">list</span> == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    LinkNode *pCurrent = <span class="built_in">list</span>-&gt;head-&gt;next;</span><br><span class="line">    <span class="keyword">while</span> (pCurrent != <span class="literal">NULL</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        print(pCurrent-&gt;data);</span><br><span class="line">        pCurrent = pCurrent-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><code>释放链表</code>:  清空所有元素的内存，包括链表和节点。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">void</span> <span class="title function_">FreeSpace_LinkList</span><span class="params">(LinKList *<span class="built_in">list</span>)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">list</span> == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    LinkNode *pCurrent = <span class="built_in">list</span>-&gt;head;</span><br><span class="line">    <span class="keyword">while</span> (pCurrent != <span class="literal">NULL</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">//缓存下一个节点</span></span><br><span class="line">        LinkNode *pNext = pCurrent-&gt;next;</span><br><span class="line">        <span class="built_in">free</span>(pCurrent);</span><br><span class="line">        pCurrent = pNext;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">list</span>-&gt;size = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">free</span>(<span class="built_in">list</span>);</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="4-2-双向链表"><a href="#4-2-双向链表" class="headerlink" title="4.2 双向链表"></a>4.2 双向链表</h3><p>虽然使用单链表能 100% 解决逻辑关系为 “一对一” 数据的存储问题，但在解决某些特殊问题时，单链表并不是效率最优的存储结构。比如说，如果算法中需要大量地找某指定结点的前趋结点，使用单链表无疑是灾难性的，因为单链表更适合 “从前往后” 找，而 “从后往前” 找并不是它的强项。本节来学习双向链表（简称双链表）。</p>
<p><img src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/双向链表.png" alt=""></p>
<blockquote>
<p>双向，指的是各节点之间的逻辑关系是双向的，但通常头指针只设置一个，除非实际情况需要。</p>
</blockquote>
<p>从上图中可以看到，双向链表中各节点包含以下 3 部分信息：</p>
<ol>
<li>指针域：用于指向当前节点的直接前驱节点；</li>
<li>数据域：用于存储数据元素。</li>
<li>指针域：用于指向当前节点的直接后继节点；</li>
</ol>
<p><img src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/image-20210415121701683.png" alt=""></p>
<p>数据类型：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="type">int</span> NodeDataType;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> _<span class="title">DoublelinkedNode</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    <span class="class"><span class="keyword">struct</span> _<span class="title">DoublelinkedNOde</span> *<span class="title">prior</span>;</span> <span class="comment">//指向直接前趋</span></span><br><span class="line">    NodeDataType data;</span><br><span class="line">    <span class="class"><span class="keyword">struct</span> _<span class="title">DoublelinkedNode</span> *<span class="title">next</span>;</span> <span class="comment">//指向直接后继</span></span><br><span class="line">&#125; DoubLinkNode;</span><br></pre></td></tr></table></figure>
<p>初始化一个双向链表：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">DoubLinkNode *<span class="title function_">DoubListInit</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">    DoubLinkNode *head = (DoubLinkNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(DoubLinkNode));</span><br><span class="line">    head-&gt;prior = <span class="literal">NULL</span>;</span><br><span class="line">    head-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">    head-&gt;data = <span class="number">1</span>;</span><br><span class="line">    <span class="comment">//声明一个指向首元节点的指针，方便后期向链表中添加新创建的节点</span></span><br><span class="line">    DoubLinkNode *<span class="built_in">list</span> = head;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">2</span>; i &lt;= <span class="number">5</span>; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="comment">//创建新的节点并初始化</span></span><br><span class="line">        DoubLinkNode *body = (DoubLinkNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(DoubLinkNode));</span><br><span class="line">        body-&gt;prior = <span class="literal">NULL</span>;</span><br><span class="line">        body-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">        body-&gt;data = i;</span><br><span class="line">        <span class="comment">//新节点与链表最后一个节点建立关系</span></span><br><span class="line">        <span class="built_in">list</span>-&gt;next = body;</span><br><span class="line">        body-&gt;prior = <span class="built_in">list</span>;</span><br><span class="line">        <span class="comment">//list永远指向链表中最后一个节点</span></span><br><span class="line">        <span class="built_in">list</span> = <span class="built_in">list</span>-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong><code>双向链表添加节点</code></strong>:有三种情况，分别是头部插入、中间插入和尾部插入。</p>
<p>1、<code>头部插入</code>：将新数据元素添加到表头，只需要将该元素与表头元素建立双层逻辑关系即可。</p>
<p>换句话说，假设新元素节点为 temp，表头节点为 head，则需要做以下 2 步操作即可：</p>
<ol>
<li>temp-&gt;next=head; head-&gt;prior=temp;</li>
<li>将 head 移至 temp，重新指向新的表头；</li>
</ol>
<p><img src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/双向链表头插入.png" alt="双向链表头插入"></p>
<p>2、<code>中间位置插入</code>：同<a target="_blank" rel="noopener" href="http://c.biancheng.net/view/3336.html">单链表</a>添加数据类似，双向链表中间位置添加数据需要经过以下 2 个步骤，</p>
<ol>
<li>新节点先与其直接后继节点建立双层逻辑关系；</li>
<li>新节点的直接前驱节点与之建立双层逻辑关系；</li>
</ol>
<p><img src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/双向链表中插入.png" alt=""></p>
<p>3、<code>尾部插入</code>：与添加到表头是一个道理，实现过程如下：</p>
<ol>
<li><p>找到双链表中最后一个节点；</p>
</li>
<li><p>让新节点与最后一个节点进行双层逻辑关系；</p>
<p><img src="D:\小周的部落阁\DataStructAndAlgorithms\双向链表尾插.png" alt=""></p>
</li>
</ol>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">DoubLinkNode *<span class="title function_">InsertList</span><span class="params">(DoubLinkNode *<span class="built_in">list</span>, NodeDataType data, <span class="type">int</span> pos)</span></span><br><span class="line">&#123;</span><br><span class="line">    DoubLinkNode *NewNode = (DoubLinkNode *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(DoubLinkNode));</span><br><span class="line">    NewNode-&gt;data = data;</span><br><span class="line">    NewNode-&gt;next = <span class="literal">NULL</span>;</span><br><span class="line">    NewNode-&gt;prior = <span class="literal">NULL</span>;</span><br><span class="line">    <span class="comment">//插入到链表头，要特殊考虑</span></span><br><span class="line">    <span class="keyword">if</span> (pos == <span class="number">1</span>)</span><br><span class="line">    &#123;</span><br><span class="line">        NewNode-&gt;next = <span class="built_in">list</span>;</span><br><span class="line">        <span class="built_in">list</span>-&gt;prior = NewNode;</span><br><span class="line">        <span class="built_in">list</span> = NewNode;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//插入链表中</span></span><br><span class="line">    <span class="keyword">else</span></span><br><span class="line">    &#123;</span><br><span class="line">        DoubLinkNode *pCurrent = <span class="built_in">list</span>; <span class="comment">//辅助指针，找到插入位置的前一个节点</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; pos - <span class="number">1</span>; i++)</span><br><span class="line">        &#123;</span><br><span class="line">            pCurrent = pCurrent-&gt;next;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">if</span> (pCurrent-&gt;next == <span class="literal">NULL</span>) <span class="comment">//说明插入点是尾部</span></span><br><span class="line">        &#123;</span><br><span class="line">            pCurrent-&gt;next = NewNode;</span><br><span class="line">            NewNode-&gt;prior = pCurrent;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> <span class="comment">//说明插入点是中间</span></span><br><span class="line">        &#123;</span><br><span class="line">            pCurrent-&gt;next-&gt;prior = NewNode;</span><br><span class="line">            NewNode-&gt;next = pCurrent-&gt;next;</span><br><span class="line">            pCurrent-&gt;next = NewNode;</span><br><span class="line">            NewNode-&gt;prior = pCurrent;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">list</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p><strong><code>双向链表删除节点</code></strong>:双链表删除结点时，只需遍历链表找到要删除的结点，然后将该节点从表中摘除即可。</p>
<p><img src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/双向链表删除.png" alt=""></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">DoubLinkNode *<span class="title function_">DeleteNodeByData</span><span class="params">(DoubLinkNode *<span class="built_in">list</span>, <span class="type">int</span> data)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">list</span> == <span class="literal">NULL</span>)</span><br><span class="line">        <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">    DoubLinkNode *pCurrent = <span class="built_in">list</span>;</span><br><span class="line">    <span class="keyword">while</span> (pCurrent)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span> (pCurrent-&gt;data == data)</span><br><span class="line">        &#123;</span><br><span class="line"></span><br><span class="line">            pCurrent-&gt;next-&gt;prior = pCurrent-&gt;prior;</span><br><span class="line">            <span class="comment">//pCurrent-&gt;prior-&gt;next = pCurrent-&gt;next;</span></span><br><span class="line">            <span class="built_in">free</span>(pCurrent);</span><br><span class="line">            <span class="keyword">return</span> <span class="built_in">list</span>;</span><br><span class="line">        &#125;</span><br><span class="line">        pCurrent = pCurrent-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;tThis list doesn&#x27;t have this element\n&quot;</span>);</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">list</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p><strong><code>双向链表查找节点</code></strong>:通常，双向链表同单链表一样，都仅有一个头指针。因此，双链表查找指定元素的实现同单链表类似，都是从表头依次遍历表中元素。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br></pre></td><td class="code"><pre><span class="line"></span><br><span class="line">NodeDataType <span class="title function_">selectElem</span><span class="params">(DoubLinkNode *<span class="built_in">list</span>, NodeDataType elem)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="comment">//新建一个指针t，初始化为头指针 head</span></span><br><span class="line">    DoubLinkNode *t = <span class="built_in">list</span>;</span><br><span class="line">    <span class="type">int</span> i = <span class="number">1</span>;</span><br><span class="line">    <span class="keyword">while</span> (t)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">if</span> (t-&gt;data == elem)</span><br><span class="line">        &#123;</span><br><span class="line">            <span class="keyword">return</span> i;</span><br><span class="line">        &#125;</span><br><span class="line">        i++;</span><br><span class="line">        t = t-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//程序执行至此处，表示查找失败</span></span><br><span class="line">    <span class="keyword">return</span> <span class="number">-1</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<p><strong><code>双向链表更改节点</code></strong>:更改双链表中指定结点数据域的操作是在查找的基础上完成的。实现过程是：通过遍历找到存储有该数据元素的结点，直接更改其数据域即可。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//更新函数，其中，add 表示更改结点在双链表中的位置，newElem 为新数据的值</span></span><br><span class="line">DoubLinkNode *<span class="title function_">amendElem</span><span class="params">(DoubLinkNode *<span class="built_in">list</span>, <span class="type">int</span> pos, <span class="type">int</span> newElem)</span></span><br><span class="line">&#123;</span><br><span class="line">    DoubLinkNode *temp = <span class="built_in">list</span>;</span><br><span class="line">    <span class="comment">//遍历到被删除结点</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">1</span>; i &lt; pos; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        temp = temp-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    temp-&gt;data = newElem;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">list</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<h3 id="4-3-经典算法题——约瑟夫环"><a href="#4-3-经典算法题——约瑟夫环" class="headerlink" title="4.3 经典算法题——约瑟夫环"></a>4.3 经典算法题——约瑟夫环</h3><p>约瑟夫环问题，是一个经典的循环链表问题，题意是：已知 n 个人（分别用编号 1，2，3，…，n 表示）围坐在一张圆桌周围，从编号为 k 的人开始顺时针报数，数到 m 的那个人出列；他的下一个人又从 1 开始，还是顺时针开始报数，数到 m 的那个人又出列；依次重复下去，直到圆桌上剩余一个人。</p>
<p>如图 所示，假设此时圆周周围有 5 个人，要求从编号为 3 的人开始顺时针数数，数到 2 的那个人出列：</p>
<p><img src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/约瑟夫环.png" alt=""></p>
<p>出列顺序依次为：</p>
<ul>
<li>编号为 3 的人开始数 1，然后 4 数 2，所以 4 先出列；</li>
<li>4 出列后，从 5 开始数 1，1 数 2，所以 1 出列；</li>
<li>1 出列后，从 2 开始数 1，3 数 2，所以 3 出列；</li>
<li>3 出列后，从 5 开始数 1，2 数 2，所以 2 出列；</li>
<li>最后只剩下 5 自己，所以 5 胜出。</li>
</ul>
<blockquote>
<p>可能用链表的方法去模拟这个过程，N个人看作是N个链表节点，节点1指向节点2，节点2指向节点3，……，节点N-1指向节点N，节点N指向节点1，这样就形成了一个环。然后从节点1开始1、2、3……往下报数，每报到M，就把那个节点从环上删除。下一个节点接着从1开始报数。最终链表仅剩一个节点。它就是最终的胜利者。</p>
<p>缺点：要模拟整个游戏过程，时间复杂度高达O(nm)，当n，m非常大(例如上百万，上千万)的时候，几乎是没有办法在短时间内出结果的。</p>
</blockquote>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br><span class="line">45</span><br><span class="line">46</span><br><span class="line">47</span><br><span class="line">48</span><br><span class="line">49</span><br><span class="line">50</span><br><span class="line">51</span><br><span class="line">52</span><br><span class="line">53</span><br><span class="line">54</span><br><span class="line">55</span><br><span class="line">56</span><br><span class="line">57</span><br><span class="line">58</span><br><span class="line">59</span><br><span class="line">60</span><br><span class="line">61</span><br><span class="line">62</span><br><span class="line">63</span><br><span class="line">64</span><br><span class="line">65</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> <span class="title">node</span>&#123;</span></span><br><span class="line">    <span class="type">int</span> number;</span><br><span class="line">    <span class="class"><span class="keyword">struct</span> <span class="title">node</span> * <span class="title">next</span>;</span></span><br><span class="line">&#125;person;</span><br><span class="line">person * <span class="title function_">initLink</span><span class="params">(<span class="type">int</span> n)</span>&#123;</span><br><span class="line">    person * head=(person*)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(person));</span><br><span class="line">    head-&gt;number=<span class="number">1</span>;</span><br><span class="line">    head-&gt;next=<span class="literal">NULL</span>;</span><br><span class="line">    person * cyclic=head;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i=<span class="number">2</span>; i&lt;=n; i++) &#123;</span><br><span class="line">        person * body=(person*)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(person));</span><br><span class="line">        body-&gt;number=i;</span><br><span class="line">        body-&gt;next=<span class="literal">NULL</span>; </span><br><span class="line">        cyclic-&gt;next=body;</span><br><span class="line">        cyclic=cyclic-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    cyclic-&gt;next=head;<span class="comment">//首尾相连</span></span><br><span class="line">    <span class="keyword">return</span> head;</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">void</span> <span class="title function_">findAndKillK</span><span class="params">(person * head,<span class="type">int</span> k,<span class="type">int</span> m)</span>&#123;</span><br><span class="line"> </span><br><span class="line">    person * tail=head;</span><br><span class="line">    <span class="comment">//找到链表第一个结点的上一个结点，为删除操作做准备</span></span><br><span class="line">    <span class="keyword">while</span> (tail-&gt;next!=head) &#123;</span><br><span class="line">        tail=tail-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    person * p=head;</span><br><span class="line">    <span class="comment">//找到编号为k的人</span></span><br><span class="line">    <span class="keyword">while</span> (p-&gt;number!=k) &#123;</span><br><span class="line">        tail=p;</span><br><span class="line">        p=p-&gt;next;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//从编号为k的人开始，只有符合p-&gt;next==p时，说明链表中除了p结点，所有编号都出列了，</span></span><br><span class="line">    <span class="keyword">while</span> (p-&gt;next!=p) &#123;</span><br><span class="line">        <span class="comment">//找到从p报数1开始，报m的人，并且还要知道数m-1de人的位置tail，方便做删除操作。</span></span><br><span class="line">        <span class="keyword">for</span> (<span class="type">int</span> i=<span class="number">1</span>; i&lt;m; i++) &#123;</span><br><span class="line">            tail=p;</span><br><span class="line">            p=p-&gt;next;</span><br><span class="line">        &#125;</span><br><span class="line">        tail-&gt;next=p-&gt;next;<span class="comment">//从链表上将p结点摘下来</span></span><br><span class="line">        <span class="built_in">printf</span>(<span class="string">&quot;出列人的编号为:%d\n&quot;</span>,p-&gt;number);</span><br><span class="line">        <span class="built_in">free</span>(p);</span><br><span class="line">        p=tail-&gt;next;<span class="comment">//继续使用p指针指向出列编号的下一个编号，游戏继续</span></span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;出列人的编号为:%d\n&quot;</span>,p-&gt;number);</span><br><span class="line">    <span class="built_in">free</span>(p);</span><br><span class="line">&#125;</span><br><span class="line"></span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span> &#123;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;输入圆桌上的人数n:&quot;</span>);</span><br><span class="line">    <span class="type">int</span> n;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;n);</span><br><span class="line">    person * head=initLink(n);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;从第k人开始报数(k&gt;1且k&lt;%d)：&quot;</span>,n);</span><br><span class="line">    <span class="type">int</span> k;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;k);</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;数到m的人出列：&quot;</span>);</span><br><span class="line">    <span class="type">int</span> m;</span><br><span class="line">    <span class="built_in">scanf</span>(<span class="string">&quot;%d&quot;</span>,&amp;m);</span><br><span class="line">    findAndKillK(head, k, m);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h2 id="第五章-栈和队列"><a href="#第五章-栈和队列" class="headerlink" title="第五章 栈和队列"></a>第五章 栈和队列</h2><h3 id="4-1-栈"><a href="#4-1-栈" class="headerlink" title="4.1 栈"></a>4.1 栈</h3><p>同顺序表和链表一样，栈也是用来存储逻辑关系为 “一对一” 数据的线性存储结构，如图所示。</p>
<p><img src="D:\小周的部落阁\DataStructAndAlgorithms\栈png.png" alt=""><br>从图看到，栈存储结构与之前所学的线性存储结构有所差异，这缘于栈对数据 “存” 和 “取” 的过程有特殊的要求：</p>
<ol>
<li><strong>栈只能从表的一端存取数据，另一端是封闭的；</strong></li>
<li><strong>在栈中，无论是存数据还是取数据，都必须遵循”先进后出”的原则，即最先进栈的元素最后出栈。从图中数据的存储状态可判断出，元素 1 是最先进的栈。因此，当需要从栈中取出元素 1 时，根据”先进后出”的原则，需提前将元素 3 和元素 2 从栈中取出，然后才能成功取出元素 1。</strong></li>
</ol>
<p>因此，即栈是一种只能从表的一端存取数据且遵循 <strong>“先进后出”</strong> 原则的线性存储结构。</p>
<p>栈的开口端被称为栈顶；相应地，封口端被称为栈底。因此，栈顶元素指的就是距离栈顶最近的元素，拿图 2 来说，栈顶元素为元素 4；同理，栈底元素指的是位于栈最底部的元素，图中的栈底元素为元素 1。<br><img src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/栈1.gif" alt=""></p>
<h3 id="4-2-进栈和出栈"><a href="#4-2-进栈和出栈" class="headerlink" title="4.2 进栈和出栈"></a>4.2 进栈和出栈</h3><p>基于栈结构的特点，在实际应用中，通常只会对栈执行以下两种操作：</p>
<ul>
<li>向栈中添加元素，此过程被称为”进栈”（入栈或压栈）；</li>
<li>从栈中提取出指定元素，此过程被称为”出栈”（或弹栈）；</li>
</ul>
<p>栈是一种 “特殊” 的线性存储结构，因此栈的具体实现有以下两种方式：</p>
<p>顺序栈：采用顺序存储结构可以模拟栈存储数据的特点，从而实现栈存储结构；</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//栈的数据结构</span></span><br><span class="line"><span class="keyword">typedef</span> <span class="type">int</span> dataType;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> _<span class="title">LinearStack</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    dataType arr[MAX_SIZE];</span><br><span class="line">    <span class="type">int</span> size;</span><br><span class="line">&#125; LinearStack;</span><br></pre></td></tr></table></figure>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//初始化一个栈：</span></span><br><span class="line">LinearStack *<span class="title function_">StackInit</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">    LinearStack *<span class="built_in">stack</span> = (LinearStack *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(LinearStack));</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; MAX_SIZE; i++)</span><br><span class="line">        <span class="built_in">stack</span>-&gt;arr[i] = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">stack</span>-&gt;size = <span class="number">0</span>;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">stack</span>;</span><br><span class="line">&#125;</span><br><span class="line"></span><br></pre></td></tr></table></figure>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br></pre></td><td class="code"><pre><span class="line"><span class="comment">//入栈</span></span><br><span class="line">LinearStack *<span class="title function_">PushStack</span><span class="params">(LinearStack *<span class="built_in">stack</span>, dataType data)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="built_in">stack</span>-&gt;arr[<span class="built_in">stack</span>-&gt;size] = data;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;数据:%d压入栈，位置为:%d \n&quot;</span>, <span class="built_in">stack</span>-&gt;arr[<span class="built_in">stack</span>-&gt;size], <span class="built_in">stack</span>-&gt;size);</span><br><span class="line">    <span class="built_in">stack</span>-&gt;size++;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">stack</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="comment">//出栈</span></span><br><span class="line">LinearStack *<span class="title function_">PopStack</span><span class="params">(LinearStack *<span class="built_in">stack</span>)</span></span><br><span class="line">&#123;</span><br><span class="line"></span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;数据:%d出栈&quot;</span>, <span class="built_in">stack</span>-&gt;arr[<span class="built_in">stack</span>-&gt;size]);</span><br><span class="line">    <span class="built_in">stack</span>-&gt;arr[<span class="built_in">stack</span>-&gt;size] = <span class="number">0</span>;</span><br><span class="line">    <span class="built_in">stack</span>-&gt;size--;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;剩余栈长为：%d \n&quot;</span>, <span class="built_in">stack</span>-&gt;size);</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">stack</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="4-3-队列"><a href="#4-3-队列" class="headerlink" title="4.3 队列"></a>4.3 队列</h3><p>与栈结构不同的是，队列的两端都”开口”，要求数据只能从一端进，从另一端出，如图所示：</p>
<p><img src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/队列.gif" alt=""></p>
<blockquote>
<p>通常，称进数据的一端为 “队尾”，出数据的一端为 “队头”，数据元素进队列的过程称为 “入队”，出队列的过程称为 “出队”。</p>
<p>栈和队列不要混淆，栈结构是一端封口，特点是”先进后出”；而队列的两端全是开口，特点是”先进先出”。</p>
</blockquote>
<h3 id="4-4-入队和出队"><a href="#4-4-入队和出队" class="headerlink" title="4.4 入队和出队"></a>4.4 入队和出队</h3><p>由于顺序队列的底层使用的是数组，因此需预先申请一块足够大的内存空间初始化顺序队列。除此之外，为了满足顺序队列中数据从队尾进，队头出且先进先出的要求。</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br><span class="line">32</span><br><span class="line">33</span><br><span class="line">34</span><br><span class="line">35</span><br><span class="line">36</span><br><span class="line">37</span><br><span class="line">38</span><br><span class="line">39</span><br><span class="line">40</span><br><span class="line">41</span><br><span class="line">42</span><br><span class="line">43</span><br><span class="line">44</span><br></pre></td><td class="code"><pre><span class="line"><span class="keyword">typedef</span> <span class="type">int</span> datatype;</span><br><span class="line"><span class="keyword">typedef</span> <span class="class"><span class="keyword">struct</span> _<span class="title">Queue</span></span></span><br><span class="line"><span class="class">&#123;</span></span><br><span class="line">    datatype arr[MAX];</span><br><span class="line">    <span class="type">int</span> size;</span><br><span class="line">&#125; Queue;</span><br><span class="line">Queue *<span class="title function_">QueueInit</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">    Queue *<span class="built_in">queue</span> = (Queue *)<span class="built_in">malloc</span>(<span class="keyword">sizeof</span>(<span class="built_in">queue</span>));</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; MAX; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">queue</span>-&gt;arr[i] = <span class="literal">NULL</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">queue</span>-&gt;size = <span class="number">0</span>;</span><br><span class="line">&#125;</span><br><span class="line"><span class="type">void</span> <span class="title function_">PushQueue</span><span class="params">(Queue *<span class="built_in">queue</span>, datatype data)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">queue</span> == <span class="literal">NULL</span> || <span class="built_in">queue</span>-&gt;size == MAX)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">queue</span>-&gt;arr[<span class="built_in">queue</span>-&gt;size] = data;</span><br><span class="line">    <span class="built_in">queue</span>-&gt;size++;</span><br><span class="line">&#125;</span><br><span class="line"><span class="type">void</span> <span class="title function_">PopQueue</span><span class="params">(Queue *<span class="built_in">queue</span>)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">queue</span> == <span class="literal">NULL</span> || <span class="built_in">queue</span>-&gt;size == MAX)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = <span class="number">0</span>; i &lt; <span class="built_in">queue</span>-&gt;size - <span class="number">1</span>; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="built_in">queue</span>-&gt;arr[i] = <span class="built_in">queue</span>-&gt;arr[i + <span class="number">1</span>];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="built_in">queue</span>-&gt;size--;</span><br><span class="line">&#125;</span><br><span class="line">datatype <span class="title function_">BackTopQueue</span><span class="params">(Queue *<span class="built_in">queue</span>)</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="keyword">if</span> (<span class="built_in">queue</span> == <span class="literal">NULL</span> || <span class="built_in">queue</span>-&gt;size == MAX)</span><br><span class="line">    &#123;</span><br><span class="line">        <span class="keyword">return</span>;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">return</span> <span class="built_in">queue</span>-&gt;arr[<span class="built_in">queue</span>-&gt;size];</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="4-5-栈和队列的应用"><a href="#4-5-栈和队列的应用" class="headerlink" title="4.5 栈和队列的应用"></a>4.5 栈和队列的应用</h3><p>基于栈结构对数据存取采用 “先进后出” 原则的特点，它可以用于实现很多功能。</p>
<p>例如，我们经常使用浏览器在各种网站上查找信息。假设先浏览的页面 A，然后关闭了页面 A 跳转到页面 B，随后又关闭页面 B 跳转到了页面 C。而此时，我们如果想重新回到页面 A，有两个选择：</p>
<ul>
<li>重新搜索找到页面 A；</li>
<li>使用浏览器的”回退”功能。浏览器会先回退到页面 B，而后再回退到页面 A。</li>
</ul>
<p>浏览器 “回退” 功能的实现，底层使用的就是栈存储结构。当你关闭页面 A 时，浏览器会将页面 A 入栈；同样，当你关闭页面 B 时，浏览器也会将 B入栈。因此，当你执行回退操作时，才会首先看到的是页面 B，然后是页面 A，这是栈中数据依次出栈的效果。</p>
<p>不仅如此，栈存储结构还可以帮我们检测代码中的括号匹配问题。多数编程语言都会用到括号（小括号、中括号和大括号），括号的错误使用（通常是丢右括号）会导致程序编译错误，而很多开发工具中都有检测代码是否有编辑错误的功能，其中就包含检测代码中的括号匹配问题，此功能的底层实现使用的就是栈结构。</p>
<p>同时，栈结构还可以实现数值的进制转换功能。例如，编写程序实现从十进制数自动转换成二进制数，就可以使用栈存储结构来实现。</p>
<p>以上也仅是栈应用领域的冰山一角，这里不再过多举例。在后续章节的学习中，我们会大量使用到栈结构。接下来，我们学习如何实现顺序栈和链栈，以及对栈中元素进行入栈和出栈的操作。</p>
<h2 id="第六章-串"><a href="#第六章-串" class="headerlink" title="第六章 串"></a>第六章 串</h2><p>数据结构中，字符串要单独用一种存储结构来存储，称为串存储结构。这里的串指的就是字符串。严格意义上讲，串存储结构也是一种线性存储结构，因为字符串中的字符之间也具有”一对一”的逻辑关系。只不过，与之前所学的线性存储结构不同，串结构只用于存储字符类型的数据。</p>
<p>无论学习哪种编程语言，操作最多的总是字符串。数据结构中，根据串中存储字符的数量及特点，对一些特殊的串进行了命名，比如说：</p>
<ul>
<li>空串：存储 0 个字符的串，例如 S = “”（双引号紧挨着）；</li>
<li>空格串：只包含空格字符的串，例如 S = “   “（双引号包含 5 个空格）；</li>
<li>子串和主串：假设有两个串 a 和 b，如果 a 中可以找到几个连续字符组成的串与 b 完全相同，则称 a 是 b 的主串，b 是 a 的子串。例如，若 a = “shujujiegou”，b = “shuju”，由于 a 中也包含 “shuju”，因此串 a 和串 b 是主串和子串的关系；</li>
</ul>
<p>另外，对于具有主串和子串关系的两个串，通常会让你用算法找到子串在主串的位置。子串在主串中的位置，指的是子串首个字符在主串中的位置。</p>
<p>例如，串 a = “shujujiegou”，串 b = “jiegou”，通过观察，可以判断 a 和 b 是主串和子串的关系，同时子串 b 位于主串 a 中第 6 的位置，因为在串 a 中，串 b 首字符 ‘j’ 的位置是 6。</p>
<h3 id="6-1-串的定长顺序存储"><a href="#6-1-串的定长顺序存储" class="headerlink" title="6.1 串的定长顺序存储"></a>6.1 串的定长顺序存储</h3><blockquote>
<p>串的定长顺序存储结构，可以简单地理解为采用 “固定长度的顺序存储结构” 来存储字符串，因此限定了其底层实现只能使用静态数组。</p>
</blockquote>
<p>使用定长顺序存储结构存储字符串时，需结合目标字符串的长度，预先申请足够大的内存空间。例如，采用定长顺序存储结构存储 “www.codezhou.club”，通过目测得知此字符串长度为 17，因此我们申请的数组空间长度至少为 18（最后一位存储字符串的结束标志 ‘\0’），用 C 语言表示为：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">char</span> str[<span class="number">18</span>] = “www.codezhou.club<span class="string">&quot;;</span></span><br></pre></td></tr></table></figure>
<h3 id="6-2-串的堆分配存储"><a href="#6-2-串的堆分配存储" class="headerlink" title="6.2 串的堆分配存储"></a>6.2 串的堆分配存储</h3><p>串的堆分配存储其具体实现方式是采用动态数组存储字符串。通常，编程语言会将程序占有的内存空间分成多个不同的区域，程序包含的数据会被分门别类并存储到对应的区域。拿 C 语言来说，程序会将内存分为 4 个区域，分别为堆区、栈区、数据区和代码区。</p>
<p>与其他区域不同，堆区的内存空间需要程序员手动使用 malloc 函数申请，并且在不用后要手动通过 free 函数将其释放。</p>
<p>C 语言中使用 malloc 函数最多的场景是给数组分配空间，这类数组称为动态数组。例如：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">char</span> * a = (<span class="type">char</span>*)<span class="built_in">malloc</span>(<span class="number">5</span>*<span class="keyword">sizeof</span>(<span class="type">char</span>));</span><br></pre></td></tr></table></figure>
<p>此行代码创建了一个动态数组 a，通过使用 malloc 申请了 5 个 char 类型大小的堆存储空间。</p>
<p>==动态数组相比普通数组（静态数组）的优势是长度可变，换句话说，根据需要动态数组可额外申请更多的堆空间（使用 relloc 函数）：==</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br></pre></td><td class="code"><pre><span class="line">a = (<span class="type">char</span>*)<span class="built_in">realloc</span>(a, <span class="number">10</span>*<span class="keyword">sizeof</span>(<span class="type">char</span>));</span><br></pre></td></tr></table></figure>
<p>通过使用这行代码，之前具有 5 个 char 型存储空间的动态数组，其容量扩大为可存储 10 个 char 型数据。</p>
<p>完整展示如下：</p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br><span class="line">22</span><br><span class="line">23</span><br><span class="line">24</span><br><span class="line">25</span><br><span class="line">26</span><br><span class="line">27</span><br><span class="line">28</span><br><span class="line">29</span><br><span class="line">30</span><br><span class="line">31</span><br></pre></td><td class="code"><pre><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stdio.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;stdlib.h&gt;</span></span></span><br><span class="line"><span class="meta">#<span class="keyword">include</span> <span class="string">&lt;string.h&gt;</span></span></span><br><span class="line"><span class="type">int</span> <span class="title function_">main</span><span class="params">()</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">char</span> *a1 = <span class="literal">NULL</span>;</span><br><span class="line">    <span class="type">char</span> *a2 = <span class="literal">NULL</span>;</span><br><span class="line">    a1 = (<span class="type">char</span> *)<span class="built_in">malloc</span>(<span class="number">10</span> * <span class="keyword">sizeof</span>(<span class="type">char</span>));</span><br><span class="line">    <span class="built_in">strcpy</span>(a1, <span class="string">&quot;http://www&quot;</span>); <span class="comment">//将字符串&quot;http://www&quot;复制给a1</span></span><br><span class="line">    a2 = (<span class="type">char</span> *)<span class="built_in">malloc</span>(<span class="number">10</span> * <span class="keyword">sizeof</span>(<span class="type">char</span>));</span><br><span class="line">    <span class="built_in">strcpy</span>(a2, <span class="string">&quot;codezhou.club&quot;</span>);</span><br><span class="line">    <span class="type">int</span> lengthA1 = <span class="built_in">strlen</span>(a1); <span class="comment">//a1串的长度</span></span><br><span class="line">    <span class="type">int</span> lengthA2 = <span class="built_in">strlen</span>(a2); <span class="comment">//a2串的长度</span></span><br><span class="line">    <span class="comment">//尝试将合并的串存储在 a1 中，如果 a1 空间不够，则用realloc动态申请</span></span><br><span class="line">    <span class="keyword">if</span> (lengthA1 &lt; lengthA1 + lengthA2)</span><br><span class="line">    &#123;</span><br><span class="line">        a1 = (<span class="type">char</span> *)<span class="built_in">realloc</span>(a1, (lengthA1 + lengthA2 + <span class="number">1</span>) * <span class="keyword">sizeof</span>(<span class="type">char</span>));</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//合并两个串到 a1 中</span></span><br><span class="line">    <span class="keyword">for</span> (<span class="type">int</span> i = lengthA1; i &lt; lengthA1 + lengthA2; i++)</span><br><span class="line">    &#123;</span><br><span class="line">        a1[i] = a2[i - lengthA1];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="comment">//串的末尾要添加 \0，避免出错</span></span><br><span class="line">    a1[lengthA1 + lengthA2] = <span class="string">&#x27;\0&#x27;</span>;</span><br><span class="line">    <span class="built_in">printf</span>(<span class="string">&quot;%s&quot;</span>, a1);</span><br><span class="line">    <span class="comment">//用完动态数组要立即释放</span></span><br><span class="line">    <span class="built_in">free</span>(a1);</span><br><span class="line">    <span class="built_in">free</span>(a2);</span><br><span class="line">    <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<h3 id="6-3-BF算法"><a href="#6-3-BF算法" class="headerlink" title="6.3 BF算法"></a>6.3 BF算法</h3><p>暴力(Brute Force)算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和 T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较下去，直到得出最后的匹配结果。BF算法是一种蛮力算法。</p>
<p><img src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/20210507125343.png" style="zoom:80%;" /></p>
<figure class="highlight c"><table><tr><td class="gutter"><pre><span class="line">1</span><br><span class="line">2</span><br><span class="line">3</span><br><span class="line">4</span><br><span class="line">5</span><br><span class="line">6</span><br><span class="line">7</span><br><span class="line">8</span><br><span class="line">9</span><br><span class="line">10</span><br><span class="line">11</span><br><span class="line">12</span><br><span class="line">13</span><br><span class="line">14</span><br><span class="line">15</span><br><span class="line">16</span><br><span class="line">17</span><br><span class="line">18</span><br><span class="line">19</span><br><span class="line">20</span><br><span class="line">21</span><br></pre></td><td class="code"><pre><span class="line"><span class="type">int</span> <span class="title function_">index</span><span class="params">( String S, String T, <span class="type">int</span> pos )</span></span><br><span class="line">&#123;</span><br><span class="line">    <span class="type">int</span> i = pos;                        <span class="comment">// i 表示主串 S 中当前位置下标</span></span><br><span class="line">    <span class="type">int</span> j = <span class="number">1</span>;                            <span class="comment">// j 表示子串 T 中当前位置下标</span></span><br><span class="line">    <span class="keyword">while</span>( i &lt;= S[<span class="number">0</span>] &amp;&amp; j &lt;= T[<span class="number">0</span>] )&#123;    <span class="comment">// i 或 j 其中一个到达尾部则终止搜索</span></span><br><span class="line">        <span class="keyword">if</span>( S[i] == T[i] )&#123;             <span class="comment">// 若相等则继续进行下一个元素匹配</span></span><br><span class="line">            i++;</span><br><span class="line">            j++;</span><br><span class="line">        &#125;</span><br><span class="line">        <span class="keyword">else</span> &#123;                         <span class="comment">// 若匹配失败则 j 回溯到第一个元素重新匹配</span></span><br><span class="line">            i = i - j + <span class="number">2</span>;              <span class="comment">// 将 i 重新回溯到上次匹配首位的下一个元素</span></span><br><span class="line">            j = <span class="number">1</span>;</span><br><span class="line">        &#125;</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">if</span>( j &gt; T[<span class="number">0</span>] )&#123;</span><br><span class="line">        <span class="keyword">return</span> i - T[<span class="number">0</span>];</span><br><span class="line">    &#125;</span><br><span class="line">    <span class="keyword">else</span> &#123;</span><br><span class="line">        <span class="keyword">return</span> <span class="number">0</span>;</span><br><span class="line">    &#125;</span><br><span class="line">&#125;</span><br></pre></td></tr></table></figure>
<p>BF算法时间复杂度:该算法最理想的时间复杂度 <code>O(n)</code>，n 表示串 A 的长度，即第一次匹配就成功。BF 算法最坏情况的时间复杂度为 <code>O(n*m)</code>，n 为串 A 的长度，m 为串 B 的长度。例如，串 B 为 “0000000001”，而串 A 为 “01”，这种情况下，两个串每次匹配，都必须匹配至串 A 的最末尾才能判断匹配失败，因此运行了 n*m 次。</p>
<p>BF 算法的实现过程很 “无脑”，不包含任何技巧，在对数据量大的串进行模式匹配时，算法的效率很低。</p>
<h3 id="6-4-KMP算法"><a href="#6-4-KMP算法" class="headerlink" title="6.4 KMP算法"></a>6.4 KMP算法</h3><blockquote>
<p>在<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/计算机科学">计算机科学</a>中，<strong>Knuth-Morris-Pratt<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/字符串查找算法">字符串查找算法</a></strong>（简称为<strong>KMP算法</strong>）可在一个<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/字符串">字符串</a><code>S</code>内查找一个词<code>W</code>的出现位置。一个词在不匹配时本身就包含足够的信息来确定下一个匹配可能的开始位置，此算法利用这一特性以避免重新检查先前匹配的<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/字符">字符</a>。</p>
<p>这个算法由<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/wiki/高德纳">高德纳</a>和<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/w/index.php?title=沃恩·普拉特&amp;action=edit&amp;redlink=1">沃恩·普拉特</a>在1974年构思，同年<a target="_blank" rel="noopener" href="https://zh.wikipedia.org/w/index.php?title=詹姆斯·H·莫里斯&amp;action=edit&amp;redlink=1">詹姆斯·H·莫里斯</a>也独立地设计出该算法，最终三人于1977年联合发表。</p>
</blockquote>
<h2 id="第七章-二叉树"><a href="#第七章-二叉树" class="headerlink" title="第七章 二叉树"></a>第七章 二叉树</h2></article><div class="post-copyright"><div class="post-copyright__author"><span class="post-copyright-meta">文章作者: </span><span class="post-copyright-info"><a href="https://gitee.com/zwyywz/zwyywz.git">Zhouwy</a></span></div><div class="post-copyright__type"><span class="post-copyright-meta">文章链接: </span><span class="post-copyright-info"><a href="https://gitee.com/zwyywz/zwyywz.git/2021/03/26/DataStructAndAlgorithms/">https://gitee.com/zwyywz/zwyywz.git/2021/03/26/DataStructAndAlgorithms/</a></span></div><div class="post-copyright__notice"><span class="post-copyright-meta">版权声明: </span><span class="post-copyright-info">本博客所有文章除特别声明外，均采用 <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/" target="_blank">CC BY-NC-SA 4.0</a> 许可协议。转载请注明来自 <a href="https://gitee.com/zwyywz/zwyywz.git" target="_blank">啊粥啊周舟の部落阁</a>！</span></div></div><div class="tag_share"><div class="post-meta__tag-list"><a class="post-meta__tags" href="/zwyywz/tags/%E7%AE%97%E6%B3%95/">算法</a><a class="post-meta__tags" href="/zwyywz/tags/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84/">数据结构</a><a class="post-meta__tags" href="/zwyywz/tags/C/">C++</a></div><div class="post_share"><div class="social-share" data-image="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/数据结构与算法.jpg" data-sites="facebook,twitter,wechat,weibo,qq"></div><link rel="stylesheet" href="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/css/share.min.css" media="print" onload="this.media='all'"><script src="https://cdn.jsdelivr.net/npm/butterfly-extsrc/sharejs/dist/js/social-share.min.js" defer></script></div></div><div class="post-reward"><div class="reward-button"><i class="fas fa-qrcode"></i> 打赏</div><div class="reward-main"><ul class="reward-all"><li class="reward-item"><a href="/zwyywz/img/wechat.jpg" target="_blank"><img class="post-qr-code-img" src="/zwyywz/img/wechat.jpg" alt="微信"/></a><div class="post-qr-code-desc">微信</div></li><li class="reward-item"><a href="/zwyywz/img/alipay.jpg" target="_blank"><img class="post-qr-code-img" src="/zwyywz/img/alipay.jpg" alt="支付宝"/></a><div class="post-qr-code-desc">支付宝</div></li></ul></div></div><nav class="pagination-post" id="pagination"><div class="prev-post pull-left"><a href="/zwyywz/2021/03/31/opencv%E5%AE%89%E8%A3%85%E6%95%99%E7%A8%8B/" title="【树莓派】OpenCV3源码方式安装教程"><img class="cover" src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/OpenCV.png" onerror="onerror=null;src='/zwyywz/img/404.jpg'" alt="cover of previous post"><div class="pagination-info"><div class="label">上一篇</div><div class="prev_info">【树莓派】OpenCV3源码方式安装教程</div></div></a></div><div class="next-post pull-right"><a href="/zwyywz/2020/09/20/Mac%20M1%20Pro%20%E6%B7%B1%E5%BA%A6%E5%AD%A6%E4%B9%A0%E7%8E%AF%E5%A2%83%E6%90%AD%E5%BB%BA/" title="Mac M1 Pro 深度学习环境搭建"><img class="cover" src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/apple-macbook-pro-m1-2020-5-20230410110609763.jpg" onerror="onerror=null;src='/zwyywz/img/404.jpg'" alt="cover of next post"><div class="pagination-info"><div class="label">下一篇</div><div class="next_info">Mac M1 Pro 深度学习环境搭建</div></div></a></div></nav><div class="relatedPosts"><div class="headline"><i class="fas fa-thumbs-up fa-fw"></i><span>相关推荐</span></div><div class="relatedPosts-list"><div><a href="/zwyywz/2020/03/31/MathematicaOfMachineLearning/" title="机器学习中的数学原理"><img class="cover" src="https://blog-1300216920.cos.ap-nanjing.myqcloud.com/maths.jpg" alt="cover"><div class="content is-center"><div class="date"><i class="far fa-calendar-alt fa-fw"></i> 2020-03-31</div><div class="title">机器学习中的数学原理</div></div></a></div></div></div></div><div class="aside-content" id="aside-content"><div class="sticky_layout"><div class="card-widget" id="card-toc"><div class="item-headline"><i class="fas fa-stream"></i><span>目录</span><span class="toc-percentage"></span></div><div class="toc-content"><ol class="toc"><li class="toc-item toc-level-1"><a class="toc-link" href="#%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95-C-C-%E5%AE%9E%E7%8E%B0"><span class="toc-number">1.</span> <span class="toc-text">数据结构与算法(C&#x2F;C++实现)</span></a><ol class="toc-child"><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AC%AC%E4%B8%80%E7%AB%A0-C-%E5%9B%9E%E9%A1%BE"><span class="toc-number">1.1.</span> <span class="toc-text">第一章 C++回顾</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#1-1-C-%E5%88%9D%E6%AD%A5"><span class="toc-number">1.1.1.</span> <span class="toc-text">1.1 C++初步</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#1%E3%80%81C-%E5%91%BD%E5%90%8D%E7%A9%BA%E9%97%B4"><span class="toc-number">1.1.1.1.</span> <span class="toc-text">1、C++命名空间</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2%E3%80%81C-%E6%A0%87%E5%87%86%E5%BA%93%E5%92%8Cstd%E5%91%BD%E5%90%8D%E7%A9%BA%E9%97%B4"><span class="toc-number">1.1.1.2.</span> <span class="toc-text">2、C++标准库和std命名空间</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#3%E3%80%81new%E5%92%8Cdelete%E6%93%8D%E4%BD%9C%E7%AC%A6"><span class="toc-number">1.1.1.3.</span> <span class="toc-text">3、new和delete操作符</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4%E3%80%81inline-%E5%86%85%E8%81%94%E5%87%BD%E6%95%B0"><span class="toc-number">1.1.1.4.</span> <span class="toc-text">4、inline 内联函数</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-2-C-%E5%87%BD%E6%95%B0%E6%8F%90%E9%AB%98"><span class="toc-number">1.1.2.</span> <span class="toc-text">1.2 C++ 函数提高</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#1%E3%80%81%E5%87%BD%E6%95%B0%E5%8F%82%E6%95%B0"><span class="toc-number">1.1.2.1.</span> <span class="toc-text">1、函数参数</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2%E3%80%81%E5%87%BD%E6%95%B0%E9%87%8D%E8%BD%BD"><span class="toc-number">1.1.2.2.</span> <span class="toc-text">2、函数重载</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#3%E3%80%81%E6%A8%A1%E6%9D%BF%E5%87%BD%E6%95%B0"><span class="toc-number">1.1.2.3.</span> <span class="toc-text">3、模板函数</span></a></li></ol></li><li class="toc-item toc-level-3"><a class="toc-link" href="#1-3-C-%E7%B1%BB%E5%92%8C%E5%AF%B9%E8%B1%A1"><span class="toc-number">1.1.3.</span> <span class="toc-text">1.3 C++类和对象</span></a><ol class="toc-child"><li class="toc-item toc-level-4"><a class="toc-link" href="#1%E3%80%81%E5%B0%81%E8%A3%85%E7%9A%84%E6%84%8F%E4%B9%89"><span class="toc-number">1.1.3.1.</span> <span class="toc-text">1、封装的意义</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#2%E3%80%81%E5%AF%B9%E8%B1%A1%E7%9A%84%E5%88%9D%E5%A7%8B%E5%8C%96%E5%92%8C%E6%B8%85%E7%90%86"><span class="toc-number">1.1.3.2.</span> <span class="toc-text">2、对象的初始化和清理</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#3%E3%80%81%E5%87%BD%E6%95%B0%E6%A8%A1%E6%9D%BF"><span class="toc-number">1.1.3.3.</span> <span class="toc-text">3、函数模板</span></a></li><li class="toc-item toc-level-4"><a class="toc-link" href="#4%E3%80%81%E7%B1%BB%E6%A8%A1%E6%9D%BF"><span class="toc-number">1.1.3.4.</span> <span class="toc-text">4、类模板</span></a></li></ol></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AC%AC%E4%BA%8C%E7%AB%A0-%E7%A8%8B%E5%BA%8F%E6%80%A7%E8%83%BD%E5%88%86%E6%9E%90"><span class="toc-number">1.2.</span> <span class="toc-text">第二章 程序性能分析</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#2-1-%E7%A9%BA%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">1.2.1.</span> <span class="toc-text">2.1 空间复杂度</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-2-%E6%97%B6%E9%97%B4%E5%A4%8D%E6%9D%82%E5%BA%A6"><span class="toc-number">1.2.2.</span> <span class="toc-text">2.2 时间复杂度</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-3-%E6%93%8D%E4%BD%9C%E8%AE%A1%E6%95%B0"><span class="toc-number">1.2.3.</span> <span class="toc-text">2.3 操作计数</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#2-4-%E6%AD%A5%E6%95%B0"><span class="toc-number">1.2.4.</span> <span class="toc-text">2.4 步数</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AC%AC%E4%B8%89%E7%AB%A0-%E7%BA%BF%E6%80%A7%E8%A1%A8%E2%80%94%E2%80%94%E6%95%B0%E7%BB%84%E6%8F%8F%E8%BF%B0"><span class="toc-number">1.3.</span> <span class="toc-text">第三章  线性表——数组描述</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#3-1-%E7%BA%BF%E6%80%A7%E8%A1%A8%E7%9A%84%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84"><span class="toc-number">1.3.1.</span> <span class="toc-text">3.1 线性表的数据结构</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#3-2-%E5%8F%98%E9%95%BF%E4%B8%80%E7%BB%B4%E6%95%B0%E7%BB%84"><span class="toc-number">1.3.2.</span> <span class="toc-text">3.2 变长一维数组</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AC%AC%E5%9B%9B%E7%AB%A0-%E7%BA%BF%E6%80%A7%E8%A1%A8%E2%80%94%E2%80%94-%E9%93%BE%E8%A1%A8"><span class="toc-number">1.4.</span> <span class="toc-text">第四章 线性表—— 链表</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#4-1-%E5%8D%95%E5%90%91%E9%93%BE%E8%A1%A8"><span class="toc-number">1.4.1.</span> <span class="toc-text">4.1 单向链表</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-2-%E5%8F%8C%E5%90%91%E9%93%BE%E8%A1%A8"><span class="toc-number">1.4.2.</span> <span class="toc-text">4.2 双向链表</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-3-%E7%BB%8F%E5%85%B8%E7%AE%97%E6%B3%95%E9%A2%98%E2%80%94%E2%80%94%E7%BA%A6%E7%91%9F%E5%A4%AB%E7%8E%AF"><span class="toc-number">1.4.3.</span> <span class="toc-text">4.3 经典算法题——约瑟夫环</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AC%AC%E4%BA%94%E7%AB%A0-%E6%A0%88%E5%92%8C%E9%98%9F%E5%88%97"><span class="toc-number">1.5.</span> <span class="toc-text">第五章 栈和队列</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#4-1-%E6%A0%88"><span class="toc-number">1.5.1.</span> <span class="toc-text">4.1 栈</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-2-%E8%BF%9B%E6%A0%88%E5%92%8C%E5%87%BA%E6%A0%88"><span class="toc-number">1.5.2.</span> <span class="toc-text">4.2 进栈和出栈</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-3-%E9%98%9F%E5%88%97"><span class="toc-number">1.5.3.</span> <span class="toc-text">4.3 队列</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-4-%E5%85%A5%E9%98%9F%E5%92%8C%E5%87%BA%E9%98%9F"><span class="toc-number">1.5.4.</span> <span class="toc-text">4.4 入队和出队</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#4-5-%E6%A0%88%E5%92%8C%E9%98%9F%E5%88%97%E7%9A%84%E5%BA%94%E7%94%A8"><span class="toc-number">1.5.5.</span> <span class="toc-text">4.5 栈和队列的应用</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AC%AC%E5%85%AD%E7%AB%A0-%E4%B8%B2"><span class="toc-number">1.6.</span> <span class="toc-text">第六章 串</span></a><ol class="toc-child"><li class="toc-item toc-level-3"><a class="toc-link" href="#6-1-%E4%B8%B2%E7%9A%84%E5%AE%9A%E9%95%BF%E9%A1%BA%E5%BA%8F%E5%AD%98%E5%82%A8"><span class="toc-number">1.6.1.</span> <span class="toc-text">6.1 串的定长顺序存储</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-2-%E4%B8%B2%E7%9A%84%E5%A0%86%E5%88%86%E9%85%8D%E5%AD%98%E5%82%A8"><span class="toc-number">1.6.2.</span> <span class="toc-text">6.2 串的堆分配存储</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-3-BF%E7%AE%97%E6%B3%95"><span class="toc-number">1.6.3.</span> <span class="toc-text">6.3 BF算法</span></a></li><li class="toc-item toc-level-3"><a class="toc-link" href="#6-4-KMP%E7%AE%97%E6%B3%95"><span class="toc-number">1.6.4.</span> <span class="toc-text">6.4 KMP算法</span></a></li></ol></li><li class="toc-item toc-level-2"><a class="toc-link" href="#%E7%AC%AC%E4%B8%83%E7%AB%A0-%E4%BA%8C%E5%8F%89%E6%A0%91"><span class="toc-number">1.7.</span> <span class="toc-text">第七章 二叉树</span></a></li></ol></li></ol></div></div></div></div></main><footer id="footer"><div id="footer-wrap"><div class="copyright">&copy;2020 - 2023 By Zhouwy</div><div class="framework-info"><span>框架 </span><a target="_blank" rel="noopener" href="https://hexo.io">Hexo</a><span class="footer-separator">|</span><span>主题 </span><a target="_blank" rel="noopener" href="https://github.com/jerryc127/hexo-theme-butterfly">Butterfly</a></div></div></footer></div><div id="rightside"><div id="rightside-config-hide"><button id="readmode" type="button" title="阅读模式"><i class="fas fa-book-open"></i></button><button id="translateLink" type="button" title="简繁转换">简</button><button id="darkmode" type="button" title="浅色和深色模式转换"><i class="fas fa-adjust"></i></button><button id="hide-aside-btn" type="button" title="单栏和双栏切换"><i class="fas fa-arrows-alt-h"></i></button></div><div id="rightside-config-show"><button id="rightside_config" type="button" title="设置"><i class="fas fa-cog fa-spin"></i></button><button class="close" id="mobile-toc-button" type="button" title="目录"><i class="fas fa-list-ul"></i></button><button id="go-up" type="button" title="回到顶部"><span class="scroll-percent"></span><i class="fas fa-arrow-up"></i></button></div></div><div><script src="/zwyywz/js/utils.js"></script><script src="/zwyywz/js/main.js"></script><script src="/zwyywz/js/tw_cn.js"></script><script src="https://cdn.jsdelivr.net/npm/@fancyapps/ui/dist/fancybox/fancybox.umd.min.js"></script><div class="js-pjax"><script>if (!window.MathJax) {
  window.MathJax = {
    tex: {
      inlineMath: [ ['$','$'], ["\\(","\\)"]],
      tags: 'ams'
    },
    chtml: {
      scale: 1.1
    },
    options: {
      renderActions: {
        findScript: [10, doc => {
          for (const node of document.querySelectorAll('script[type^="math/tex"]')) {
            const display = !!node.type.match(/; *mode=display/)
            const math = new doc.options.MathItem(node.textContent, doc.inputJax[0], display)
            const text = document.createTextNode('')
            node.parentNode.replaceChild(text, node)
            math.start = {node: text, delim: '', n: 0}
            math.end = {node: text, delim: '', n: 0}
            doc.math.push(math)
          }
        }, ''],
        insertScript: [200, () => {
          document.querySelectorAll('mjx-container').forEach(node => {
            if (node.hasAttribute('display')) {
              btf.wrap(node, 'div', { class: 'mathjax-overflow' })
            } else {
              btf.wrap(node, 'span', { class: 'mathjax-overflow' })
            }
          });
        }, '', false]
      }
    }
  }
  
  const script = document.createElement('script')
  script.src = 'https://cdn.jsdelivr.net/npm/mathjax/es5/tex-mml-chtml.min.js'
  script.id = 'MathJax-script'
  script.async = true
  document.head.appendChild(script)
} else {
  MathJax.startup.document.state(0)
  MathJax.texReset()
  MathJax.typesetPromise()
}</script></div><script async data-pjax src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js"></script></div></body></html>